提出 #68222250

---

ソースコード 拡げる

// uncomment if you need to cheese
//#pragma GCC target ("avx2")
//#pragma GCC optimize ("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<iostream>
#include<vector>
#include <random>
#include <numeric>
#include <algorithm>
#include <map>
#include<queue>
#include <set>
#include <chrono>
using namespace std;
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl '\n'
typedef long long ll;
#define mod1 (ll)1000000007
#define mod2 (ll)998244353
#define pll pair<ll,ll>
typedef long double lb;

#define eps (lb)(1e-9)
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
// Operator overloads
template<typename T1, typename T2> // cin >> pair<T1, T2>
istream& operator>>(istream &istream, pair<T1, T2> &p) { return (istream >> p.first >> p.second); }
 
template<typename T> // cin >> vector<T>
istream& operator>>(istream &istream, vector<T> &v)
{
    for (auto &it : v)
        cin >> it;
    return istream;
}
 
template<typename T1, typename T2> // cout << pair<T1, T2>
ostream& operator<<(ostream &ostream, const pair<T1, T2> &p) { return (ostream << p.first << " " << p.second); }
template<typename T> // cout << vector<T>
ostream& operator<<(ostream &ostream, const vector<T> &c) { for (auto &it : c) cout << it << " "; return ostream; }
 
// Utility functions
template <typename T>
void print(T &&t)  { cout << t << "\n"; }
template <typename T, typename... Args>
void print(T &&t, Args &&... args)
{
    cout << t << " ";
    print(forward<Args>(args)...);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random(ll p){ // gives random number in [0,p]
 
 return uniform_int_distribution<ll>(0, p)(rng);
}
void bfs(vector<ll>v){

    queue<vector<ll>>q;
    q.push(v);
    set<vector<ll>>s; s.insert(v);
    while (q.size())
    {
        cout<<q.front()<<endl;
        auto v=q.front();
        q.pop();
        for(ll i(1);i<v.size();++i){
            ll a=v[i]^v[i-1];
            auto p=v;
            p.insert(p.begin()+i,a);
            if(p.size()>16){continue;}
            if(s.count(p)){continue;}
            s.insert(p);
            q.push(p);
        }
    }
    
}
pll findRuns(vector<ll>&v){
    ll run=0; // runs of 0
    ll cnt=0; // runs of 0 with size =1
    ll prev=-1;
    for(ll i(0);i<v.size();++i){
        if(v[i]==0){
            if(v[i]!=prev){
                run++;
                ll nex=-1;
                if( (i+1)<v.size()){nex=v[i+1];}
                if(v[i]!=nex){cnt++;}
            }
        }
        prev=v[i];
    }
    return {run,cnt};
}
void solve();
int main() {
io;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ll t=1,n=1;
// cin>>t;
while (t--){
     solve();
    }
     return 0;
}
void solve(){  
    ll n;
    cin>>n;
    vector<ll>v(n);
    cin>>v;
    ll sum=accumulate(all(v),0ll);
    v.insert(begin(v),-1);
    v.insert(begin(v),-1);
    v.push_back(-1);
    v.push_back(-1);
    ll run=0; // runs of 0
    ll cnt=0; // runs of 0 with size =1
    for(ll i(2);i<=(n+1);++i){
        if(v[i]==0){
            if(v[i]!=v[i-1]){
                run++;
                if(v[i]!=v[i+1]){
                    cnt++;
                }
            }
        }
    }
    // cout<<run<<" "<<cnt<<endl;
    // indices in range [2,n+1] 
    ll q;
    cin>>q;
    while (q--)
    {
        ll ind;
        cin>>ind;
        ind++;
        // cout<<v<<endl;
        // we can only look at v[ind-2]...v[ind+2] // 5 elements
        pll cur,nex;
        {
            vector<ll>p(v.begin()+ind-2,v.begin()+ind+3);
            cur=findRuns(p);
            // cout<<p<<"->"<<cur<<endl;
            p[2]^=1;
            nex=findRuns(p);
            // cout<<p<<"->"<<nex<<endl;
            nex.first-=cur.first,nex.second-=cur.second;
            sum-=v[ind];
            sum+=(v[ind]^1);
            v[ind]^=1;

            run+=nex.first,cnt+=nex.second;
            
        }
        // now we have runs and count lets go;
        if(sum==0){
            cout<<2<<endl;
        }
        else if(sum==n){
            cout<<n<<endl;
        }
        else{
            ll ans=0;
            if((v[2]==v[n+1])){
                ans=2;
                if(v[2]==0){
                    // 0,0
                    ans++;
                ll d=run-cnt; // runs of zero with >=1 0
                if(v[2]==0){
                    if(v[3]==0){
                        d--;
                        ans++;
                    }
                }
                if(v[n+1]==0){
                    if(v[n]==0){
                        d--;
                        ans++;
                    }
                }
                ans+=3*d;
                }
                else{
                    ll d =run -cnt;
                    if(d>0){
                        d--;
                        ans+=2;
                    }
                    ans+=3*d;
                }

                
            }
            else{
                ans=2;
                // 1,0 or 0,1
                ll d=run-cnt; // runs of zero with >=1 0
                if(v[2]==0){
                    if(v[3]==0){
                        d--;
                        ans++;
                    }
                }
                if(v[n+1]==0){
                    if(v[n]==0){
                        d--;
                        ans++;
                    }
                }
                // cout<<d<<"$$$"<<endl;
                // 0, 1
                ans+=(3*d);

            }
            cout<<ans<<endl;
        }


        
        
    }
    
}
// Do not get stuck on a single approach for long, think of multiple ways

提出情報

コンパイルエラー

Main.cpp: In function ‘void bfs(std::vector<long long int>)’:
Main.cpp:83:22: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   83 |         for(ll i(1);i<v.size();++i){
      |                     ~^~~~~~~~~
Main.cpp: In function ‘std::pair<long long int, long long int> findRuns(std::vector<long long int>&)’:
Main.cpp:99:18: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   99 |     for(ll i(0);i<v.size();++i){
      |                 ~^~~~~~~~~
Main.cpp:104:26: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  104 |                 if( (i+1)<v.size()){nex=v[i+1];}
      |                     ~~~~~^~~~~~~~~
Main.cpp: In function ‘int main()’:
Main.cpp:117:8: warning: unused variable ‘n’ [-Wunused-variable]
  117 | ll t=1,n=1;
      |        ^

ジャッジ結果