Submission #1054009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054009		huutuan	Secret Permutation (RMI19_permutation)	C++14	53.33 / 100	17 ms	344 KiB

permutation

#include "permutation.h"

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(69420);

int rand(int l, int r){
   return uniform_int_distribution<int>(l, r)(rng);
}

void solve(int n) {
   if (n==3){
      if (query({1, 2, 3})==2) answer({1, 2, 3});
      if (query({2, 1, 3})==2) answer({2, 1, 3});
      answer({3, 1, 2});
   }
   vector<int> ans(n+1, -1);
   int x=rand(1, n);
   int y=x;
   while (y==x) y=rand(1, n);
   if (x>y) swap(x, y);
   map<int, int> cnt;
   vector<int> dx(n+1), dy(n+1), sum(n+1);
   int diff=0;
   for (int i=1; i<=n; ++i) if (i!=x && i!=y){
      vector<int> v;
      v.push_back(i);
      v.push_back(y);
      v.push_back(x);
      for (int j=1; j<=n; ++j) if (j!=i && j!=x && j!=y) v.push_back(j);
      int d=-query(v);
      sum[i]=-d;
      swap(v[0], v[1]);
      d+=query(v);
      dx[i]=d;
      diff=min(diff, d);
   }
   diff=max(1, -diff+1);
   int mx=0;
   vector<int> cand;
   for (int i=1; i<=n; ++i) if (i!=x && i!=y){
      dx[i]+=diff;
      mx=max(mx, dx[i]);
   }
   for (int i=1; i<=n; ++i) if (i!=x && i!=y){
      if (dx[i]==mx) cand.push_back(i);
   }
   if (diff==n-1){
      ans[x]=1; ans[y]=n;
   }else{
      int x1=mx+1, x2=n-mx;
      int y1=x1+diff, y2=x2+diff;
      vector<int> vis(n+1);
      if (cand.size()==2){
         ans[x]=x1; ans[y]=y1;
         vis[x1]=vis[y1]=1;
      }else{
         int id=cand[0];
         vector<int> v;
         v.push_back(id);
         v.push_back(x);
         v.push_back(y);
         for (int j=1; j<=n; ++j) if (j!=id && j!=x && j!=y) v.push_back(j);
         int d=-query(v);
         swap(v[0], v[1]);
         d+=query(v)+diff;
         if (x1>=1 && x1<=n && y1>=1 && y1<=n && y1==d+1){
            ans[x]=x1; ans[y]=y1; ans[id]=1;
         }else{
            ans[x]=x2; ans[y]=y2; ans[id]=n;
         }
         dy[id]=abs(ans[id]-ans[y]);
         vis[ans[x]]=vis[ans[y]]=vis[ans[id]]=1;
      }
   }
   for (int i=1; i<=n; ++i) if (ans[i]==-1){
      int t1=ans[x]+dx[i], t2=ans[x]-dx[i];
      if (t1<1 || t1>n) ans[i]=t2;
      else if (t2<1 || t2>n) ans[i]=t1;
      else{
         vector<int> v;
         v.push_back(i);
         v.push_back(x);
         v.push_back(y);
         for (int j=1; j<=n; ++j) if (j!=i && j!=x && j!=y) v.push_back(j);
         int d=-query(v);
         swap(v[0], v[1]);
         d+=query(v)+diff;
         if (dx[i]+d==diff) ans[i]=ans[x]+dx[i];
         else if (dx[i]<d) ans[i]=ans[x]-dx[i];
         else ans[i]=ans[x]+dx[i];
      }
   }
   ans.erase(ans.begin());
   answer(ans);
}

Compilation message (stderr)

stub.cpp: In function 'int query(int*)':
stub.cpp:15:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   fscanf(stdin, "%d", &x);
      |   ~~~~~~^~~~~~~~~~~~~~~~~
stub.cpp: In function 'int main(int, char**)':
stub.cpp:48:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   fscanf(stdin, "%d", &N);
      |   ~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 7.999994999999999 / 15
• Subtask 2: 18.666655 / 35
• Subtask 3: 26.666649999999997 / 50