Submission #817212

#TimeUsernameProblemLanguageResultExecution timeMemory
817212t6twotwoParking (CEOI22_parking)C++17
50 / 100
84 ms8952 KiB
#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){ int a=x[i]/2; int b=y[i]/2; if(top[b]!=-1) swap(a,b); move(a,b); }; auto get=[&](){ if(free.em){ cout<<-1; exit(0); } int t=free.bk; free.ppb; return t; }; FOR(i,M){ if(top[i]==-1&&bot[i]!=-1){ int j=i,k=bot[i]; while(x[k]%2!=y[k]%2){ j^=(x[k]/2)^(y[k]/2); park(k); k=bot[j]; } } } // FOR(i,N) if((x[i]%2==1||top[x[i]/2]==-1)&&(y[i]%2==1||top[y[i]/2]==-1)) park(i); vc<bool> vis(M); FOR(i,M){ if(vis[i]||bot[i]==top[i])continue; vis[i]=1; int k=bot[i],f=0,j=top[i]==-1?(i^(x[k]/2)^(y[k]/2)):i; vc<int> S{k}; vc<vc<int>> T; while(1){ T.pb({}); vis[j]=1; k=f?bot[j]:top[j]; while(k!=-1&&k!=bot[i]&&x[k]%2!=y[k]%2){ T.bk.pb(k); j^=(x[k]/2)^(y[k]/2); vis[j]=1; k=f?bot[j]:top[j]; } if (k==bot[i]||k==-1)break; S.pb(k); j^=(x[k]/2)^(y[k]/2); f^=1; } if(top[i]==-1){ FFOR(j,1,sz(S)-2,2){ int t=get(); move(x[S[j]]/2,t); move(y[S[j]]/2,t); ROF(k,sz(T[j-1])) park(T[j-1][k]); FOR(k,sz(T[j])) park(T[j][k]); park(S[j-1]); } park(S.bk); }else{ if (sz(S)==1){ int t=get(); int a=x[S[0]]; int b=y[S[0]]; if (a%2==0) swap(a,b); move(a/2,t); ROF(j,sz(T[0])) park(T[0][j]); move(b/2,t); continue; } int t=get(); move(x[S[1]]/2,t); move(y[S[1]]/2,t); ROF(j,sz(T[0])) park(T[0][j]); FOR(j,sz(T[1])) park(T[1][j]); FFOR(j,3,sz(S)-1,2){ int t=get(); move(x[S[j]]/2,t); move(y[S[j]]/2,t); ROF(k,sz(T[j-1])) park(T[j-1][k]); FOR(k,sz(T[j])) park(T[j][k]); park(S[j-1]); } park(S[0]); if(sz(S)%2){ ROF(j,sz(T.bk)) park(T.bk[j]); park(S.bk); } } } cout<<sz(ans)<<"\n"; for(auto[x,y]:ans){ cout<<x+1<<" "<<y+1<<"\n"; } return 6/22; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...