제출 #1259748

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1259748		user736482	Alternating Current (BOI18_alternating)	C++20	100 / 100	51 ms	16048 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<pair<ll,ll>,ll>>wej;//dlugosc,pocz
ll nxt[100007],pop[100007],co[100007];
vector<ll>v[100007];
ll sm1[100007],sm2[100007];
vector<pair<pair<ll,ll>,ll>>usu,uzy;
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;
        wej.pb({{b-a,a},i});
    }
    sort(wej.begin(),wej.end());
    reverse(wej.begin(),wej.end());
    for(ll i=0;i<m;i++){
        wej[i].ff={wej[i].ff.ss,wej[i].ff.ff+wej[i].ff.ss};
    }
    set<pair<pair<ll,ll>,ll>>s;
    for(auto i : wej){
        if(s.empty()){
            uzy.pb(i);
            s.insert(i);
        }
        else{
            if((*s.begin()).ff.ff<=i.ff.ff){
                auto ak=*--s.lower_bound({{i.ff.ff,INFL},INFL});
                if(ak.ff.ss>=i.ff.ss){
                    usu.pb(i);
                    co[i.ss]=ak.ss;
                    v[ak.ss].pb(i.ss);
                }
                else{
                    uzy.pb(i);

                    s.insert(i);
                }
            }
            else{
                auto ak=*--s.end();
                if(ak.ff.ss-n>=i.ff.ss){
                    usu.pb(i);
                    v[ak.ss].pb(i.ss);
                    co[i.ss]=ak.ss;
                }
                else{
                    uzy.pb(i);
                    s.insert(i);
                }
            }
        }
    }
    sort(uzy.begin(),uzy.end());
    for(auto i : usu){
        auto j=i.ff;
     //   cout<<j.ff<<" "<<j.ss<<"\n";
        if(j.ss>=n){
            sm1[0]++;
            sm1[j.ss-n]--;
            sm1[j.ff]++;
            sm1[n]--;
        }
        else{
            sm1[j.ss]--;
            sm1[j.ff]++;
        }
    }
   // cout<<"\n";
    for(auto i : uzy){
        auto j=i.ff;
     //   cout<<j.ff<<" "<<j.ss<<"\n";
        if(j.ss>=n){
            sm2[0]++;
            sm2[j.ss-n]--;
            sm2[j.ff]++;
            sm2[n]--;
        }
        else{
            sm2[j.ss]--;
            sm2[j.ff]++;
        }
    }
    
    sm2[0]+=sm1[0];
    for(ll i=1;i<n;i++){
        sm2[i]+=sm1[i]+sm2[i-1];
        sm1[i]+=sm1[i-1];
    }
    ll strt=-1;
    uzy.pb(uzy[0]);
    uzy.back().ff.ff+=n;
     uzy.pb(uzy[1]);
    uzy.back().ff.ff+=n;
    for(ll i=0;i<uzy.size()-2;i++){
        auto j=uzy[i].ff;
        auto k=uzy[i+1].ff;
        auto o=uzy[i+2].ff;
        bool bl=1;
        for(ll p=k.ff;p<j.ss && p<o.ff;p++){
            if(sm2[p%n]<3)bl=0;
        }
        if(bl==1)strt=(i+1)%(uzy.size());
    }

    uzy.pop_back();
    uzy.pop_back();
    for(ll i=0;i<n;i++){
       // cout<<sm1[i]<<" "<<sm2[i]<<"\n";
    }
    if(uzy.size()%2==0)strt=0;
    else if(strt==-1){
        cout<<"impossible";return 0;
    }
    for(ll i=0;i<n;i++){
        if(sm2[i]<2){
            cout<<"impossible";return 0;
        }
    }
    bool bl=0;
    for(ll i=strt;i<strt+(uzy.size());i++){
        st(uzy[i%uzy.size()].ss,bl);
        bl^=1;
    }
    for(ll i=0;i<m;i++)cout<<co[i];
}

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