Submission #930903

#	Time	Username	Problem	Language	Result	Execution time	Memory
930903		huutuan	Mouse (info1cup19_mouse)	C++14	100 / 100	46 ms	960 KiB

mouse

#include "grader.h"
#include<bits/stdc++.h>

using namespace std;

static const int N=500;
static bool done;
static int n;

int fake_query(vector<int> Q){
   if (done) return 0;
   int tmp=query(Q);
   if (tmp==n) done=1;
   return tmp;
}

static mt19937 rng(69420);

vector<vector<pair<int, int>>> round_robin(int m){
   vector<int> v(m+(m&1));
   iota(v.begin(), v.end(), 0);
   vector<vector<pair<int, int>>> ans;
   int cnt=m+(m&1)-1;
   for (int i=0; i<cnt; ++i){
      ans.emplace_back();
      for (int j=0; j<(int)v.size()/2; ++j){
         int x=v[j], y=v[(int)v.size()-j-1];
         if (x<m && y<m) ans.back().emplace_back(x, y);
      }
      v.insert(v.begin()+1, v.back());
      v.pop_back();
   }
   return ans;
}

static vector<int> g[N];
static int vis[N];
static vector<int> path, cycle;

void dfs(int u, int p){
   path.push_back(u);
   vis[u]=1;
   bool pp=0;
   for (int v:g[u]){
      if (v==p && !pp){
         pp=1;
         continue;
      }
      if (vis[v]){
         if (cycle.empty()) cycle=path;
      }else dfs(v, u);
   }
   path.pop_back();
}

void solve(int _n) {
   n=_n;
   vector<int> p(n);
   vector<int> mark(n);
   iota(p.begin(), p.end(), 1);
   while (fake_query(p)) shuffle(p.begin(), p.end(), rng);
   auto order=round_robin(n);
   auto get_swapped=[&](const vector<pair<int, int>> &v, int pos) -> vector<int> {
      auto q=p;
      for (int i=0; i<=pos; ++i) swap(q[v[i].first], q[v[i].second]);
      return q;
   };
   vector<pair<int, int>> edges;
   for (auto &i:order){
      int pos=(int)i.size()-1, cnt=fake_query(get_swapped(i, pos));
      while (cnt){
         int l=0, r=pos-1;
         int prv=-1;
         while (l<=r){
            int mid=(l+r)>>1;
            int tmp=fake_query(get_swapped(i, mid));
            if (tmp==cnt) r=mid-1;
            else l=mid+1, prv=tmp;
         }
         if (prv==-1) prv=fake_query(get_swapped(i, r));
         edges.push_back(i[l]);
         if (cnt-prv==2) edges.push_back(i[l]);
         pos=r;
         cnt=prv;
      }
   }
   for (auto &i:edges){
      g[i.first].push_back(i.second);
      g[i.second].push_back(i.first);
   }
   auto get_shifted=[&](const vector<int> &cyc) -> vector<int> {
      auto q=p;
      int tmp=q[cyc[0]];
      for (int i=0; i<(int)cyc.size()-1; ++i) q[cyc[i]]=q[cyc[i+1]];
      q[cyc.back()]=tmp;
      return q;
   };
   vector<int> ans=p;
   auto shift=[&](const vector<int> &cyc) -> void {
      int tmp=ans[cyc[0]];
      for (int i=0; i<(int)cyc.size()-1; ++i) ans[cyc[i]]=ans[cyc[i+1]];
      ans[cyc.back()]=tmp;
   };
   for (int i=0; i<n; ++i) if (!vis[i]){
      cycle.clear();
      dfs(i, -1);
      if ((int)cycle.size()>=2){
         int tmp=fake_query(get_shifted(cycle));
         if (tmp) shift(cycle);
         else{
            reverse(cycle.begin(), cycle.end());
            shift(cycle);
         }
         tmp=fake_query(get_shifted(cycle));
      }
   }
   fake_query(ans);
}

• Subtask 1: 13 / 13
• Subtask 2: 38 / 38
• Subtask 3: 49 / 49