Submission #1259521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259521		user736482	Alternating Current (BOI18_alternating)	C++20	0 / 100	3096 ms	11956 KiB

alternating

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000007
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099LL

ll n,m,a,b,c;
vector<pair<ll,ll>>kon[100007];
ll nxt[100007],pop[100007],co[100007];
vector<ll>v[100007];
void st(ll x,ll y){
    co[x]=y;
    for(ll i : v[x])st(i,y^1);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(ll i=0;i<n;i++){
        nxt[i]=(i+1)%n;
        pop[i]=(i+n-1)%n;
    }
    for(ll i=0;i<m;i++){
        co[i]=-1;
        cin>>a>>b;
        a--;
        b%=n;
        if(b<=a)b+=n;
        kon[a].pb({b,i});
    }
    ll akbst=0;
    ll kto=-1;
    bool bl=1;
    while(bl){
        bl=0;
        for(ll i=0;i<n;i++){
           // cout<<i<<" "<<flush;
          //  for(ll j=0;j<n;j++){
              //  cout<<"\n";
              //  cout<<pop[j]<<" "<<nxt[j]<<"   ";
              //  for(auto  k: kon[j])cout<<k.ff<<" ";
              //  cout<<"\n";
           // }
            //cout<<kon[i].size()<<" ";
            //cout<<"\n\n";
            //cout<<flush;
            sort(kon[i].begin(),kon[i].end());
            reverse(kon[i].begin(),kon[i].end());
            vector<pair<ll,ll>>pom;
            bool bl2=0;
            for(auto j : kon[i]){
                //cout<<akbst<<" "<<kto<<" "<<j.ff<<" "<<j.ss<<"\n";
                if(j.ff<=akbst){
                   // cout<<j.ff<<" "<<akbst<<flush;
                    bl=1;
               //     co[j.ss]=kto;
                    v[kto].pb(j.ss);
                    ll idx=nxt[i];
                    
                    while(idx<=j.ff){
                        for(auto k : kon[idx])pom.pb(k);
                        kon[idx].clear();
                        nxt[pop[idx]]=nxt[idx];
                        pop[nxt[idx]]=pop[idx];
                        idx=nxt[idx];
                    }
                    
                }
                else{
                    bl2=1;
                    kto=j.ss;
                    akbst=j.ff;
                }
            }
            if(kon[i].size()){
                kon[i]={kon[i][0]};
                if(bl2==0)kon[i].pop_back();
            }
            for(auto k : pom)kon[i].pb(k);
            if(pom.size()){
                i--;
                continue;
            }
            
        }
        akbst-=n;
        
    }
    //cout<<"\n\n\n";
    for(ll i=0;i<n;i++){
        //cout<<i<<": ";
        //for(auto j : kon[i])cout<<j.ff<<" ";
        //cout<<"\n"<<flush;
    }
    ll idx=0;
    for(idx;kon[idx].empty();idx++);
    ll ak=idx;
    while(1){
        //cout<<ak<<" "<<kon[ak][0].ss<<"  "<<flush;
        ll zas=kon[ak][0].ff;
        st(kon[ak][0].ss,0);
        kon[ak].clear();
        if(zas-n>=idx)break;
        ll i;
        for(i=zas;i>ak;i--){
            if(kon[i%n].size())break;
        }
        if(i==ak){
            cout<<"impossible";return 0;
        }
        ak=i;
    }
    idx=0;
    bl=0;
    for(ll i=0;i<n;i++)bl|=(bool)(kon[i].size());
    if(bl==0){
        cout<<"impossible";return 0;
    }
    for(idx;kon[idx].empty();idx++);
    ak=idx;
    while(1){
        ll zas=kon[ak][0].ff;
        st(kon[ak][0].ss,1);
        kon[ak].clear();
        if(zas-n>=idx)break;
        ll i;
        for(i=zas;i>ak;i--){
            if(kon[i%n].size())break;
        }
        if(i==ak){
            cout<<"impossible";return 0;
        }
        ak=i;
    }
    for(ll i=0;i<m;i++)cout<<co[i];
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 0 / 19
• Subtask 5: 0 / 26