Submission #1227773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227773		spetr	Parking (CEOI22_parking)	C++20	20 / 100	87 ms	30068 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;
    REP(i,M){
        cin>>bot[i]>>top[i];
        if(bot[i]){
            sz[i]++;
            pos[bot[i]-1][ pos[bot[i]-1][0]!=-1 ] = i<<1;
        }
        if(top[i]){
            sz[i]++;
            pos[top[i]-1][ pos[top[i]-1][0]!=-1 ] = i<<1|1;
            if(bot[i] && bot[i]!=top[i]){
                adj[i<<1].pb(i<<1|1);
                adj[i<<1|1].pb(i<<1);
            }
        }
        if(bot[i]==0 && top[i]==0) emp.pb(i);
    }
    // helper to get an empty spot
    auto get_empty=[&]{
        while(!emp.empty() && sz[emp.back()]>0) emp.pop_back();
        if(emp.empty()){ cout<<-1; exit(0); }
        return emp.back();
    };
    // connect color pairs
    REP(c,N) if(pos[c][0]!=(pos[c][1]^1)){
        int u=pos[c][0], v=pos[c][1];
        if(u>=0&&v>=0){ adj[u].pb(v); adj[v].pb(u);}    
    }
    vector<pii> res;
    auto mv=[&](int x,int y){
        int ux=x>>1, uy=y>>1;
        res.pb({ux,uy});
        if(--sz[ux]==0) emp.pb(ux);
        sz[uy]++;
    };
    // solve path
    auto solve_path=[&](vector<int>& path){
        int n=path.size();
        for(int i=0;i<n;i+=2){
            if(path[i+1]&1) mv(path[i+1],path[i]);
            else{
                int p=n;
                for(int j=i;j<n;j+=2) if((path[j]&1)&&(path[j+1]&1)){ p=j; break; }
                if(p<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;
            }
        }
    };
    vector<bool> used(2*M,false);
    vector<vector<int>> paths, cycles;
    vector<int> cnt_pt;
    // 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]=1; 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;
        }
        int cnt=0;
        for(int j=0;j+1<path.size();j+=2) if((path[j]&1)&&(path[j+1]&1)) cnt++;
        paths.pb(path); cnt_pt.pb(cnt);
    }
    vector<int> order(paths.size()); iota(all(order),0);
    sort(all(order),[&](int a,int b){return cnt_pt[a]<cnt_pt[b];});
    for(int i:order) solve_path(paths[i]);
    // delete edge helper
    auto del_edge=[&](int x,int y){
        adj[x].erase(find(all(adj[x]),y));
        adj[y].erase(find(all(adj[y]),x));
    };
    // extract cycles
    REP(i,2*M) if(!used[i] && adj[i].size()==2){
        vector<int> cyc;
        int u=i, p=-1;
        while(!used[u]){ used[u]=1; cyc.pb(u);
            int nxt= (adj[u][0]==p?adj[u][1]:adj[u][0]);
            p=u; u=nxt;
        }
        cyc.pb(cyc[0]);
        cycles.pb(cyc);
    }
    // solve cycles
    for(auto &cycle:cycles){
        int m=cycle.size(); int p=-1;
        for(int i=0;i+1<m;i++) if((cycle[i]&1)&&(cycle[i+1]&1)){ p=i; break; }
        if(p!=-1){
            int e=get_empty()<<1;
            mv(cycle[p],e); mv(cycle[p+1],e);
            int prev = (p?cycle[p-1]:cycle[m-2]);
            del_edge(prev,cycle[p]); del_edge(cycle[p],cycle[p+1]);
            int next = (p+2<m?cycle[p+2]:cycle[1]);
            del_edge(cycle[p+1],next);
            cycle.erase(cycle.begin()+p, cycle.begin()+p+2);
            rotate(cycle.begin(), cycle.begin()+p, cycle.end());
            solve_path(cycle);
        } else {
            cycle.pop_back();
            if(cycle[0]&1) rotate(cycle.begin(),cycle.begin()+1,cycle.end());
            if(cycle[0]==(cycle[1]^1)){
                rotate(cycle.begin(),cycle.begin()+1,cycle.end()); reverse(all(cycle));
            }
            int e=get_empty()<<1;
            mv(cycle.back(),e);
            for(int i=1;i+2<cycle.size();i+=2) mv(cycle[i],cycle[i-1]);
            mv(cycle[cycle.size()-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: 0 / 25
• Subtask 4: 0 / 15
• Subtask 5: 0 / 25
• Subtask 6: 0 / 15