Submission #1227775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227775		spetr	Parking (CEOI22_parking)	C++20	28 / 100	138 ms	40808 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define REP(i,n) for(int i=0,_n=(n); i<_n; ++i)
#define FORE(i,a,b) for(int i=(a),_b=(b); i<=_b; ++i)

typedef pair<int,int> pii;

void process(){
    int N,M;
    cin>>N>>M;
    vector<int> bot(M), top(M);
    vector<vector<int>> pos(N, vector<int>(2,-1));
    vector<vector<int>> adj(2*M);
    vector<int> sz(M,0), emp;
    emp.reserve(M);

    // 1) Načíst bot/top, nastavit sz[i] a vyplnit emp
    REP(i,M){
        cin>>bot[i]>>top[i];
        if(bot[i]>0)  sz[i]++;
        if(top[i]>0) sz[i]++;
    }
    REP(i,M){
        if(sz[i]==0) emp.pb(i);
    }
    // 2) Naplnit pos[] a vnitro-hrany full spotů
    REP(i,M){
        if(bot[i]>0){
            int c=bot[i]-1;
            pos[c][ pos[c][0]!=-1 ] = i<<1;
        }
        if(top[i]>0){
            int c=top[i]-1;
            pos[c][ pos[c][0]!=-1 ] = i<<1|1;
            if(bot[i]>0 && bot[i]!=top[i]){
                adj[i<<1].pb(i<<1|1);
                adj[i<<1|1].pb(i<<1);
            }
        }
    }
    // 3) Pomocná lambda pro prázdný spot
    auto get_empty=[&](){
        while(!emp.empty() && sz[emp.back()]>0) emp.pop_back();
        if(emp.empty()){ cout<<-1<<"\n"; exit(0); }
        return emp.back();
    };
    // 4) Napojit dvojice stejných barev
    REP(c,N){
        int u=pos[c][0], v=pos[c][1];
        if(u>=0 && v>=0 && u!=(v^1)){
            adj[u].pb(v);
            adj[v].pb(u);
        }
    }
    // 5) Přesuny
    vector<pii> res;
    auto mv=[&](int x,int y){
        int sx=x>>1, sy=y>>1;
        res.emplace_back(sx,sy);
        // odebírám z x
        sz[sx]--;
        if(sz[sx]==0) emp.pb(sx);
        // přidávám do y
        if(sz[sy]==0){
            // pokud tam bylo nula, spot už v emp, ale dle definice
            // necháváme, get_empty se postará
        }
        sz[sy]++;
    };
    // 6) Rozplétání cest (kóduju přímo inline stejnou logiku)
    vector<bool> used(2*M,false);
    vector<vector<int>> paths, cycles;
    // 6a) extract chains
    REP(i,2*M){
        if(!used[i] && adj[i].size()==1){
            vector<int> path;
            int u=i, p=-1;
            while(true){
                used[u]=true; path.pb(u);
                int nxt=-1;
                for(int v:adj[u]) if(v!=p){ nxt=v; break; }
                if(nxt==-1) break;
                p=u; u=nxt;
            }
            paths.pb(path);
        }
    }
    // 6b) solve each chain
    for(auto &path: paths){
        int n = path.size();
        for(int i=0;i+1<n;i+=2){
            if(path[i+1]&1){
                mv(path[i+1], path[i]);
            } else {
                // najdu nejdřív top-pár
                int p=i;
                for(;p+1<n;p+=2){
                    if((path[p]&1) && (path[p+1]&1)) break;
                }
                if(p+1<n){
                    int e = get_empty()<<1;
                    mv(path[p],e);
                    mv(path[p+1],e);
                }
                for(int j=p-2;j>=i;j-=2){
                    mv(path[j], path[j+1]);
                }
                i=p;
            }
        }
    }
    // 7) extract cycles
    auto del_edge=[&](int x,int y){
        auto it=find(all(adj[x]),y);
        if(it!=adj[x].end()) adj[x].erase(it);
        it=find(all(adj[y]),x);
        if(it!=adj[y].end()) adj[y].erase(it);
    };
    REP(i,2*M){
        if(!used[i] && adj[i].size()==2){
            vector<int> cyc;
            int u=i, p=-1;
            while(!used[u]){
                used[u]=true;
                cyc.pb(u);
                int nxt = (adj[u][0]==p?adj[u][1]:adj[u][0]);
                p=u; u=nxt;
            }
            cyc.pb(cyc[0]);
            // solve one cycle inline
            int m=cyc.size(), ps=-1;
            for(int j=0;j+1<m;j++){
                if((cyc[j]&1)&&(cyc[j+1]&1)){ ps=j; break; }
            }
            if(ps>=0){
                int e = get_empty()<<1;
                mv(cyc[ps],e); mv(cyc[ps+1], e);
                int prv = (ps?cyc[ps-1]:cyc[m-2]);
                int nxt = (ps+2<m?cyc[ps+2]:cyc[1]);
                del_edge(prv, cyc[ps]);
                del_edge(cyc[ps], cyc[ps+1]);
                del_edge(cyc[ps+1], nxt);
                cyc.erase(cyc.begin()+ps, cyc.begin()+ps+2);
                rotate(cyc.begin(), cyc.begin()+ps, cyc.end());
                // zacyklení do cesty
                int nn=cyc.size();
                for(int j=0;j+1<nn;j+=2){
                    if(cyc[j+1]&1) mv(cyc[j+1],cyc[j]);
                    else{
                        int pe=j;
                        for(;pe+1<nn;pe+=2){
                            if((cyc[pe]&1)&&(cyc[pe+1]&1)) break;
                        }
                        if(pe+1<nn){
                            int ee = get_empty()<<1;
                            mv(cyc[pe],ee); mv(cyc[pe+1],ee);
                        }
                        for(int k=pe-2;k>=j;k-=2)
                            mv(cyc[k],cyc[k+1]);
                        j=pe;
                    }
                }
            } else {
                cyc.pop_back();
                if(cyc[0]&1){
                    rotate(cyc.begin(),cyc.begin()+1,cyc.end());
                }
                if(cyc[0]==(cyc[1]^1)){
                    rotate(cyc.begin(),cyc.begin()+1,cyc.end());
                    reverse(all(cyc));
                }
                int e = get_empty()<<1;
                mv(cyc.back(), e);
                int szc=cyc.size();
                for(int j=1;j+2<szc;j+=2) mv(cyc[j],cyc[j-1]);
                mv(cyc[szc-2], e);
            }
        }
    }

    cout<<res.size()<<"\n";
    for(auto &p:res) cout<<p.fi+1<<" "<<p.se+1<<"\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    process();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 5 / 25
• Subtask 4: 3 / 15
• Subtask 5: 0 / 25
• Subtask 6: 0 / 15