Submission #1259595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259595		user736482	Alternating Current (BOI18_alternating)	C++20	0 / 100	971 ms	1114112 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];
                    if(j.ff%n==i){
                        for(ll i=0;i<m;i++){
                            if(co[i]==-1)st(i,1);
                        }
                        for(ll i=0;i<m;i++)cout<<co[i];
                        return 0;
                    }
                    ll x=0;
                    while(idx>i ^ j.ff%n>=i ^ j.ff%n>=idx){
                        x++;
                       // if(x==2137)return 0;
                      //  cout<<idx<<"  ";
                        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<n;i++){
        if(kon[i].size())st(kon[i][0].ss,0);
    }
    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