oj.uz

Submission #930903

# Submission time Handle Problem Language Result Execution time Memory
930903 2024-02-20T16:38:10 Z huutuan Mouse (info1cup19_mouse) C++14
100 / 100
 46 ms 960 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Correct! Number of queries: 21
2 Correct 0 ms 344 KB Correct! Number of queries: 10
3 Correct 0 ms 344 KB Correct! Number of queries: 16
4 Correct 0 ms 344 KB Correct! Number of queries: 21
5 Correct 0 ms 344 KB Correct! Number of queries: 25
6 Correct 0 ms 344 KB Correct! Number of queries: 30

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Correct! Number of queries: 21
2 Correct 0 ms 344 KB Correct! Number of queries: 10
3 Correct 0 ms 344 KB Correct! Number of queries: 16
4 Correct 0 ms 344 KB Correct! Number of queries: 21
5 Correct 0 ms 344 KB Correct! Number of queries: 25
6 Correct 0 ms 344 KB Correct! Number of queries: 30
7 Correct 3 ms 716 KB Correct! Number of queries: 300
8 Correct 2 ms 712 KB Correct! Number of queries: 300
9 Correct 2 ms 468 KB Correct! Number of queries: 300
10 Correct 2 ms 452 KB Correct! Number of queries: 300
11 Correct 2 ms 456 KB Correct! Number of queries: 300
12 Correct 2 ms 708 KB Correct! Number of queries: 300
13 Correct 2 ms 712 KB Correct! Number of queries: 300
14 Correct 2 ms 716 KB Correct! Number of queries: 300
15 Correct 3 ms 720 KB Correct! Number of queries: 300
16 Correct 2 ms 468 KB Correct! Number of queries: 300

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Correct! Number of queries: 21
2 Correct 0 ms 344 KB Correct! Number of queries: 10
3 Correct 0 ms 344 KB Correct! Number of queries: 16
4 Correct 0 ms 344 KB Correct! Number of queries: 21
5 Correct 0 ms 344 KB Correct! Number of queries: 25
6 Correct 0 ms 344 KB Correct! Number of queries: 30
7 Correct 3 ms 716 KB Correct! Number of queries: 300
8 Correct 2 ms 712 KB Correct! Number of queries: 300
9 Correct 2 ms 468 KB Correct! Number of queries: 300
10 Correct 2 ms 452 KB Correct! Number of queries: 300
11 Correct 2 ms 456 KB Correct! Number of queries: 300
12 Correct 2 ms 708 KB Correct! Number of queries: 300
13 Correct 2 ms 712 KB Correct! Number of queries: 300
14 Correct 2 ms 716 KB Correct! Number of queries: 300
15 Correct 3 ms 720 KB Correct! Number of queries: 300
16 Correct 2 ms 468 KB Correct! Number of queries: 300
17 Correct 46 ms 716 KB Correct! Number of queries: 2000
18 Correct 36 ms 712 KB Correct! Number of queries: 2000
19 Correct 33 ms 912 KB Correct! Number of queries: 1900
20 Correct 35 ms 716 KB Correct! Number of queries: 2000
21 Correct 35 ms 716 KB Correct! Number of queries: 2000
22 Correct 32 ms 716 KB Correct! Number of queries: 1900
23 Correct 33 ms 716 KB Correct! Number of queries: 2000
24 Correct 39 ms 960 KB Correct! Number of queries: 2000
25 Correct 45 ms 712 KB Correct! Number of queries: 2000
26 Correct 36 ms 720 KB Correct! Number of queries: 2000