Submission #69251

#TimeUsernameProblemLanguageResultExecution timeMemory
69251Sa1378Unscrambling a Messy Bug (IOI16_messy)C++17
20 / 100
3 ms512 KiB
#include <bits/stdc++.h> #include "messy.h" using namespace std; #define N ((int)201) int n,ans[N]; string now; string ok(int p) { string s=now; if(p)for(int i=0;i<n;i++)s[i]=((s[i]=='0')?'1':'0'); return s; } void ask(int l,int r) { if(l>=r-1)return ; if(l==r-2) { now[l]='1';add_element(ok(0));now[l]='0'; return ; } int mid=(l+r+1)/2; now[l]='1';add_element(ok(0));now[l]='0'; for(int i=l+1;i<mid;i++)now[i]='1',add_element(ok(1)),now[i]='0'; now[l]='1'; ask(l+1,mid);ask(mid,r); now[l]='0'; return ; } void solve(int l,int r,vector <int> valid) { // cout<<l<<" "<<r<<"||| \n"; // for(auto u:valid)cout<<u<<" ";cout<<"\n"; if(l>=r)return ; if(l==r-1){ans[l]=valid[0];return ;} int id=-1; for(int p=0;p<valid.size();p++) { int i=valid[p]; if(now[i]=='1')continue; now[i]='1'; // cout<<ok(0)<<"\n"; if(p==(int)valid.size()-1 || check_element(ok(0))) { id=i;ans[l]=id; now[i]='0';// now[id] is 1 //cout<<id<<"..\n"; break; } now[i]='0'; } if(l==r-2) { for(auto i:valid) if(i!=ans[l]) ans[r-1]=i; return ; } // cout<<id<<"..\n"; int mid=(l+r+1)/2; vector <int> valid_lft,valid_rght; for(auto i:valid) if(now[i]=='0') { now[i]='1'; // cout<<ok(1)<<"\n"; if(valid_rght.size()==r-mid || check_element(ok(1))) valid_lft.push_back(i);//cout<<i<<"\n"; else if(i!=id)valid_rght.push_back(i); now[i]='0'; } now[id]='1'; solve(l+1,mid,valid_lft); solve(mid,r,valid_rght); now[id]='0'; } vector<int> restore_permutation(int m, int w, int r) { n=m; for(int i=0;i<n;i++)now+='0'; ask(0,n); compile_set(); vector <int> res; for(int i=0;i<n;i++)res.push_back(i); solve(0,n,res); for(int i=0;i<n;i++)res[ans[i]]=i;//,cout<<i<<" "<<ans[i]<<"\n";; return res; }

Compilation message (stderr)

messy.cpp: In function 'void solve(int, int, std::vector<int>)':
messy.cpp:40:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int p=0;p<valid.size();p++)
              ~^~~~~~~~~~~~~
messy.cpp:70:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(valid_rght.size()==r-mid || check_element(ok(1)))
       ~~~~~~~~~~~~~~~~~^~~~~~~
#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...