Submission #1207828

#TimeUsernameProblemLanguageResultExecution timeMemory
1207828quickslothPermutation Game (APIO25_permgame)C++20
36 / 100
1 ms328 KiB
#include <vector> using namespace std; template<class C> using vc=vector<C>; #define For(i,a,b) for(int i=(a);i<(b);i++) const int mx=400; int Bob(vc<int> t); int Alice(int m, int e, vc<int> u, vc<int> v, int n, vc<int> p) { /* graph with m vertices e edges max fixed points in permutation of size n>=m 3n steps: pick m indices, bob swaps a pair corresponding to an edge if some edge is not i-a[i] in any direction, cannot gain fixed points */ if(m==2) { // n-1 swaps For(i,0,n) if(p[i]!=i) For(j,i+1,n) if(p[j]==i) p[j]=p[i], p[i]=i, Bob({i,j}); return n; } else if(e>m) { // too many edges int ans=0; For(i,0,n) if(p[i]==i) ans++; return ans; } else if(e<m) { // not path: deg 3 // path: ? ; } else if(m==3&&e==3) { /* C_3: answer = no. odd cycles proof: if pick two from different cycles, join else if all in even cycle, swap a pair with an even gap construction: shrink cycles */ int ans=0; bool vis[mx]={}; For(i,0,n) if(!vis[i]) { vc<int> V={i}; while(p[V.back()]!=i) V.push_back(p[V.back()]); for(int t:V) vis[t]=1; if(V.size()&1) { ans++; while(V.size()>1) { // operate on last 3 int res=Bob({V[V.size()-3],V[V.size()-2],V[V.size()-1]}); int x=u[res], y=v[res]; if(x==1||y==1) break; // got fixed point V.pop_back(), V.pop_back(); } } } return ans; } else { /* not cycle: deg 3 cycle: ? */ } throw(0); }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...