Submission #1053996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053996		huutuan	Secret Permutation (RMI19_permutation)	C++14	53.14 / 100	26 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);
   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);
      swap(v[0], v[1]);
      d+=query(v);
      dx[i]=d;
      diff=min(diff, d);
   }
   diff=max(1, -diff+1);
   int mx=0;
   for (int i=1; i<=n; ++i) if (i!=x && i!=y){
      dx[i]+=diff;
      mx=max(mx, dx[i]);
   }
   int x1=mx+1, x2=n-mx;
   int y1=x1+diff, y2=x2+diff;
   for (int i=1; i<=n; ++i) if (i!=x && i!=y){
      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);
      dy[i]=d;
   }
   int my=0;
   for (int i=1; i<=n; ++i) if (i!=x && i!=y){
      dy[i]+=diff;
      my=max(my, dy[i]);
   }
   if ((x1>=1 && x1<=n && y1>=1 && y1<=n && (y1==my+1 || y1==n-my))){
      ans[x]=x1;
      ans[y]=y1;
   }else{
      ans[x]=x2;
      ans[y]=y2;
   }
   for (int i=1; i<=n; ++i) if (i!=x && i!=y){
      if (dx[i]+dy[i]==diff) ans[i]=ans[x]+dx[i];
      else if (dx[i]<dy[i]) 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.9714350000000005 / 15
• Subtask 2: 18.600015000000003 / 35
• Subtask 3: 26.571450000000002 / 50