Submission #1259847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259847		Szymon_Pilipczuk	Alternating Current (BOI18_alternating)	C++20	52 / 100	3096 ms	26552 KiB

alternating

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(),a.end()
#define rep(a,b) for(int a = 0;a<b;a++)
const int inf = 1e9;
const ll infl = 1e18;
int ans[100000];
bool cc[100000];
vector<pair<int,int>> test;
int sp;
int n,m;
void mod(int &a)
{
    a = (a+n-sp)%n;
}
void mod2(int &a)
{
    a = n-a-1;
}
int main()
{
    
    cin>>n>>m;
    vector<pair<int,int>> l(m);
    int c = 0;
    vector<vector<int>> ev;
    test.resize(m);
    pair<int,int> mx = {-1,-1};
    rep(i,m)
    {
        cin>>l[i].st>>l[i].nd;
        test[i] = l[i];
        l[i].st--;l[i].nd--;
        if(l[i].nd < l[i].st)
        {
            c++;
            cc[i] = true;
            if(mx.st < n-(l[i].st-l[i].nd+1)+2)
            {
                mx.st = n-(l[i].st-l[i].nd+1)+2;
                mx.nd = i;
            }
        }
        else
        {
            if(mx.st < l[i].nd-l[i].st+1)
            {
                mx.st = l[i].nd-l[i].st+1;
                mx.nd = i;
            }
        }
        ev.pb({l[i].st,1,i});
        ev.pb({l[i].nd+1,-1,i});
    }
    sort(all(ev));
    int j = 0;
    bool solve = true;
    int pp;
    rep(i,n)
    {
        
        while(j != m*2 && ev[j][0] == i)
        {
            if(ev[j][1] == 1)
            {
                c++;
                if(solve)cc[ev[j][2]] = true;
            }
            else
            {
                c--;
                if(solve)cc[ev[j][2]] = false;
            }
            j++;
        }
        if(c == 2)
        {
            if(solve)pp = i;
            solve = false;
            
            //cerr<<j<<"\n";
        }
        else if(c < 2)
        {
            cout<<"impossible\n";
            //end();
            return 0;
        }
    }
    //cerr<<"AAAA";
    if(solve)
    {
        //cerr<<"EEEE";
        sp = l[mx.nd].st;
        //cerr<<mx.st<<" "<<mx.nd<<" "<<l[mx.nd].st<<" "<<l[mx.nd].nd<<"\n";
        ans[mx.nd] = 1;
        pair<int,int> nx = {-1,-1};
        vector<vector<int>> p(m);
        rep(i,m)
        {
            p[i] = {(l[i].st+n-sp)%n,(l[i].nd+n-sp)%n,i};
            //cerr<<p[i][0]<<" "<<p[i][1]<<" "<<p[i][2]<<"\n";
        }
        //cerr<<mx.nd<<" "<<sp<<"\n";
        int r = p[mx.nd][1];
        sort(all(p));
        int j = 0;
        while(r < n-1)
        {
             //cerr<<r<<"\n";
            if(r == -1)
            {
                return 0;
            }
            while(j != m && p[j][0] <= r+1)
            {
                 //cerr<<p[j][0]<<" "<<p[j][1]<<" "<<p[j][2]<<"\n";
                if(p[j][1] < p[j][0])
                {
                    nx = {n-1,p[j][2]};
                    break;
                }
                if(p[j][1] > mx.st)
                {
                    nx.st = p[j][1];
                    nx.nd = p[j][2];
                }
                j++;
            }
            
            r = nx.st;
            ans[nx.nd] = 1;
        }
        rep(i,m)
        {
            cout<<ans[i];
        }
        cout<<"\n";
        //end();
    }
    else
    {
       // cerr<<"DDD\n";
        int c1,c2,p1,p2;
        pair<int,int> b1 = {-1,-1};
        pair<int,int> b2;
        pair<int,int> num;
        rep(i,m)
        {
            if(cc[i])
            {
                //cerr<<i<<"\n";
                if(b1.st == -1)
                {
                    b1 = l[i];
                    num.st = i;
                }
                else
                {
                    b2 = l[i];
                    num.nd = i;
                }
            }
        }
        if(b1.st < b2.st)
        {
            swap(b1,b2);
            swap(num.st,num.nd);
            
        }
        if(b1.st > b1.nd && b1.nd >= b2.st)
        {
            swap(b1,b2);
            swap(num.st,num.nd);
        }

        sp = pp;
       // cerr<<sp<<"\n";
        mod(b1.st);
        mod(b1.nd);
        mod(b2.st);
        mod(b2.nd);
        vector<vector<int>> p(m);
        ans[num.st] = 1;
        ans[num.nd] = 2;
        //cerr<<"\n";
        rep(i,m)
        {
            mod(l[i].st);
            mod(l[i].nd);
            p[i] = {l[i].st,l[i].nd,i};
            //cerr<<p[i][0]<<" "<<p[i][1]<<" "<<p[i][2]<<"\n";
        }
        //cerr<<"\n";
        sort(all(p));
        /*rep(i,m)
        {
            cerr<<p[i][0]<<" "<<p[i][1]<<" "<<p[i][2]<<"\n";
        }*/
        c1 = (b1.st-1+n)%n;
        c2 = (b2.st-1+n)%n;
        p1 = b1.nd;
        p2 = b2.nd;
        int j = 0;
       // cerr<<c1<<" "<<c2<<" "<<p1<<" "<<p2<<"\n";
        vector<vector<int>> k;
        bool err = false;
        while(p1 < c1 || p2 < c2)
        {
            if(p2 >= c2)
            {
                p2 = n-1;
            }
            while(j != m && p[j][0] <= min(p1,p2) + 1)
            {
                
                if(ans[p[j][2]] == 0)
                {
                    if(p[j][0] > p[j][1])
                    {
                        k.pb({n-1,p[j][2]});
                    }
                    else
                    {
                        k.pb({p[j][1],p[j][2]});
                    }
                }
                j++;
            }
            //cerr<<j<<" "<<k.size()<<" "<<p1<<" "<<p2<<" "<<c1<<" "<<c2<<"\n";
            sort(all(k));
            if(k.size() == 0)
            {
                cout<<"impossible\n";
                //end();
                return 0;
            }
            if(p1 < p2)
            {
                if(k.size() == 1)
                {
                    p1 = max(p1,k[0][0]);
                    ans[k[0][1]] = 1;
                    k.clear();
                    continue;
                }
                int i = 0;
                while(i != k.size() && k[i][0] <= max(p1,p2))
                {
                    p1 = max(p1,k[i][0]);
                    ans[k[i][1]] = 1;
                    i++;
                }
                if(i < k.size()-1)
                {
                    err = true;
                }
                else if(i == k.size()-1)
                {
                    vector<int> cu = k.back();
                    k.clear();
                    k.pb(cu);
                }
                else
                {
                    k.clear();
                }
            }
            else
            {
                if(k.size() == 1)
                {
                    p2 = max(p2,k[0][0]);
                    ans[k[0][1]] = 2;
                    k.clear();
                    continue;
                }
                int i = 0;
                while(i != k.size() && k[i][0] <= max(p1,p2))
                {
                    p2 = max(p2,k[i][0]);
                    ans[k[i][1]] = 2;
                    i++;
                }
                if(i < k.size()-1)
                {
                    err = true;
                }
                else if(i == k.size()-1)
                {
                    vector<int> cu = k.back();
                    k.clear();
                    k.pb(cu);
                }
                else
                {
                    k.clear();
                }
            }
            if(err)
            {
                break;
            }
        }
        if(err)
        {
            //cerr<<"AAA\n";
            int l1 = n;
            int l2 = c2+1;
            mod2(l1);
            mod2(l2);
            mod2(p1);
            mod2(p2);
            //cerr<<l1<<" "<<l2<<" "<<p1<<" "<<p2<<"\n";
            vector<vector<int>> u(m);
            rep(i,m)
            {
                mod2(l[i].st);
                mod2(l[i].nd);
                swap(l[i].st,l[i].nd);
                u[i] = {l[i].st,l[i].nd,i};
                //cerr<<u[i][0]<<" "<<u[i][1]<<" "<<u[i][2]<<"\n";
            }
            sort(all(u));
            rep(i,m)
            {
                if(ans[u[i][2]] != 0)
                {
                    continue;
                }
                if(l1 >= p1)
                {
                    l1 = n-1;
                }
                if(l2 >= p2)
                {
                    l2 = n-1;
                }
                if(l1 < l2)
                {
                    l1 = max(l1,u[i][1]);
                    ans[u[i][2]] = 1;
                }
                else
                {
                    l2 = max(l2,u[i][1]);
                    ans[u[i][2]] = 2;
                }
            }
        }
        rep(i,m)
        {
            if(ans[i] == 2)
            {
                cout<<0;
            }
            else
            {
                cout<<ans[i];
            }
        }
        cout<<"\n";
       // end();
    }
}

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