oj.uz

Submission #817164

# Submission time Handle Problem Language Result Execution time Memory
817164 2023-08-09T10:01:37 Z t6twotwo Parking (CEOI22_parking) C++17
10 / 100
 42 ms 5476 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FFOR(i,a,b,c) for(int i=(a);(c)>0?i<=(b):i>=(b);i+=(c))
#define FOOR(i,a,b) FFOR(i,a,(b)-1,1)
#define ROOF(i,a,b) FFOR(i,(b)-1,a,-1)
#define FOR(i,n) FOOR(i,0,n)
#define ROF(i,n) ROOF(i,0,n)
#define FORR(x,v) for(auto &x:v)
#define vc vector
#define sz(v) (int)((v).size())
#define bg begin()
#define en end()
#define em empty()
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define ppb pop_back()
#define eb emplace_back
#define bk back()
#define fr front()
#define pp pop()
#define all(v) (v).begin(),(v).end()
#define lla(v) (v).rbegin(),(v).rend()
#define f first
#define s second
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,M;
    cin>>N>>M;
    vc<int> bot(M),top(M),x(N,-1),y(N),free;
    FOR(i,M){
        cin>>bot[i]>>top[i];
        bot[i]--,top[i]--;
        if(bot[i]!=-1) (x[bot[i]]==-1?x[bot[i]]:y[bot[i]])=i*2;
        if(top[i]!=-1) (x[top[i]]==-1?x[top[i]]:y[top[i]])=i*2+1;
        if(bot[i]==-1&&top[i]==-1) free.pb(i);
    }
    vc<pair<int,int>> ans;
    auto move=[&](int u,int v) {
        ans.eb(u,v);
        int a;
        if(top[u]!=-1){
            a=top[u];
            top[u]=-1;
        }else{
            a=bot[u];
            bot[u]=-1;
        }
        if(bot[v]==-1){
            (x[a]/2==u?x[a]:y[a])=v*2;
            bot[v]=a;
        }else{
            (x[a]/2==u?x[a]:y[a])=v*2+1;
            top[v]=a;
        }
        if(bot[u]==-1){
            free.pb(u);
        }
    };
    auto park=[&](int i,bool f){
        int a=x[i]/2;
        int b=y[i]/2;
        if(f) assert(top[a]==-1||top[b]==-1);
        if(top[b]!=-1) swap(a,b);
        move(a,b);
    };
    auto check=[&](){
        if(free.em){
            cout<<-1;
            exit(0);
        }
    };
    if(2*N<=M){
        auto good=[&](int a) {
            return (x[a]%2==1||top[x[a]/2]==-1)&&(y[a]%2==1||top[y[a]/2]==-1);
        };
        vc<bool> parked(N);
        FOR(i,N){
            if(x[i]%2==1&&y[i]%2==1){
                move(x[i]/2,free.bk);
                move(y[i]/2,free.bk);
                free.ppb;
            }
            if(x[i]/2==y[i]/2) parked[i]=1;
        }
        queue<int> q;
        FOR(i,N){
            if(!parked[i]&&good(i)){
                parked[i]=1;
                q.push(i);
            }
        }
        while(!q.em){
            int i=q.fr;q.pp;
            int a=x[i]/2;
            int b=y[i]/2;
            if(top[b]!=-1) swap(a,b);
            move(a,b);
            if(bot[a]!=-1){
                if(!parked[bot[a]]&&good(bot[a])){
                    parked[bot[a]]=1;
                    q.push(bot[a]);
                }
            }
        }
        FOR(i,N){
            if(!parked[i]){
                cout<<-1;
                return 0;
            }
        }
        cout<<sz(ans)<<"\n";
        for(auto[x,y]:ans){
            cout<<x+1<<" "<<y+1<<"\n";
        }
        return 0;
    }
    vc<bool> vis(M);
    vc<vc<int>> S;
    vc<vc<vc<int>>> T;
    FOR(i,M){
        if(vis[i]||bot[i]==top[i])continue;
        int j=i,k=bot[i],f=0;
        S.pb({k});
        T.pb({});
        while(1){
            T.bk.pb({});
            vis[j]=1;
            k=f?bot[j]:top[j];
            while(k!=bot[i]&&x[k]%2!=y[k]%2){
                T.bk.bk.pb(k);
                j^=(x[k]/2)^(y[k]/2);
                vis[j]=1;
                k=f?bot[j]:top[j];
            }
            if (k==bot[i])break;
            S.bk.pb(k);
            j^=(x[k]/2)^(y[k]/2);
            f^=1;
        }
    }
    FOR(i,sz(S)){
        if (sz(S[i])==1){
            check(); int t=free.bk; free.ppb;
            int a=x[S[i][0]];
            int b=y[S[i][0]];
            if (a%2==0) swap(a,b);
            move(a/2,t);
            ROF(j,sz(T[i][0])) park(T[i][0][j],1);
            move(b/2,t);
            continue;
        }
        check(); int t=free.bk; free.ppb;
        move(x[S[i][1]]/2,t);
        move(y[S[i][1]]/2,t);
        ROF(j,sz(T[i][0])) park(T[i][0][j],1);
        FOR(j,sz(T[i][1])) park(T[i][1][j],1);
        FFOR(j,3,sz(S[i])-1,2){
            check(); int t=free.bk;free.ppb;
            move(x[S[i][j]]/2,t);
            move(y[S[i][j]]/2,t);
            ROF(k,sz(T[i][j-1])) park(T[i][j-1][k],1);
            FOR(k,sz(T[i][j])) park(T[i][j][k],1);
            park(S[i][j-1],0);
        }
        park(S[i][0],0);
        if(sz(S[i])%2){
            FOR(j,sz(T[i].bk)) park(T[i].bk[j],1);
            park(S[i].bk,0);
        }
    }
    cout<<sz(ans)<<"\n";
    for(auto[x,y]:ans){
        cout<<x+1<<" "<<y+1<<"\n";
    }
    return 6/22;
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 5284 KB Output is correct
2 Correct 42 ms 5448 KB Output is correct
3 Correct 30 ms 4360 KB Output is correct
4 Correct 34 ms 4456 KB Output is correct
5 Correct 41 ms 5476 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 724 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -