Submission #1015032

#TimeUsernameProblemLanguageResultExecution timeMemory
1015032kymMouse (info1cup19_mouse)C++14
0 / 100
1 ms344 KiB
#include <bits/stdc++.h> #ifndef LOCAL #include "grader.h" #endif using namespace std; #ifdef LOCAL void debug_out() {cerr<<endl;} template <typename Head, typename... Tail> void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);} #define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__) #else #define debug(...) #endif const int MAXN = -1; const int inf=1000000500ll; const long long oo =1000000000000000500ll; const int MOD = (int)1e9+7; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef pair<int,int> pi; #ifdef LOCAL vector<int>ans; int sz; int query(vector<int> v){ cerr<<"QUERY: "; for(int i=1;i<=sz;i++)cerr<<v[i]<<" "; cerr<<"\n"; int res=0; for(int i=1;i<=sz;i++){ res+=v[i]==ans[i]; } return res; } #endif int S; vector<int>out; vector<int>aval; void get(deque<int> vec){ // vec->numbers whose index we still dk // try to find the real index of the first guy for(auto it=vec.begin();it!=vec.end();){ if(out[*it]!=-1){ it=vec.erase(it); } else{ ++it; } } if(vec.empty())return; vector<int> lftidxes; vector<int> qq(S+1); for(int i=1;i<=S;i++){ if(aval[i]==-1)lftidxes.push_back(i); else qq[i]=aval[i]; } //cerr<<lftidxes.size()<<endl; //cerr<<"lft:"; //for(auto x:lftidxes)cout<<x<<" "; //cerr<<endl; for(int i=0;i<(int)vec.size();i++){ qq[lftidxes[i]]=vec[i]; } int oval=query(qq); if(oval==S)assert(0); vector<int> cands; for(int i=1;i<(int)vec.size();i++){ swap(qq[lftidxes[0]],qq[lftidxes[i]]); int qval=query(qq); if(qval==S)assert(0); swap(qq[lftidxes[0]],qq[lftidxes[i]]); if(qval==oval+2){ out[vec[0]]=lftidxes[i]; aval[lftidxes[i]]=vec[0]; out[vec[i]]=lftidxes[0]; aval[lftidxes[0]]=vec[i]; get(vec); return; } else if(qval==oval+1){ cands.push_back(i); } } if(cands.empty()){ // this means that the vec[0]'s real index is just lftidx[0] out[vec[0]]=lftidxes[0]; aval[lftidxes[0]]=vec[0]; get(vec); return; } if(cands.size() == 1){ assert(0); } if(cands.size() == 2){ int i0=lftidxes[0]; int i1=lftidxes[cands[0]]; int i2=lftidxes[cands[1]]; int v0=vec[0]; int v1=vec[cands[0]]; int v2=vec[cands[1]]; qq[i2]=v0; qq[i1]=v2; qq[i0]=v1; int qval=query(qq); if(qval==S)assert(0); if(qval>=oval+2){ aval[i2]=v0; aval[i0]=v1; out[v0]=i2; out[v1]=i0; get(vec); return; } else{ aval[i1]=v0; aval[i0]=v2; out[v0]=i1; out[v2]=i0; get(vec); return; } } assert(0); } void solve(int n){ S=n; // let's just try to solve index by index first out=vector<int>(S+1,-1);//what is the index of the value aval=vector<int>(S+1,-1);//what is the value of the index deque<int> vec; for(int i=1;i<=S;i++){ vec.push_back(i); } get(vec); } #ifdef LOCAL int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>sz; ans=vector<int>(sz+1); for(int i=1;i<=sz;i++){ cin>>ans[i]; } solve(sz); } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...