Submission #259610

#	Time	Username	Problem	Language	Result	Execution time	Memory
259610		dvdg6566	Secret Permutation (RMI19_permutation)	C++14	53.14 / 100	42 ms	384 KiB

permutation

#include "permutation.h"
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
const int MAXN = 300;
#define pb push_back
#define SZ(x) (int)x.size()

int firsts[MAXN];
int mids[MAXN];
int K;
int R[MAXN];

int find_diff(int pivot,int a,int b){
  vi V;
  V.pb(a);V.pb(b);V.pb(pivot);
  for(int i=1;i<=K;++i){
    if(i!=a&&i!=b&&i!=pivot)V.pb(i);
  }
  int k=query(V);
  V.clear();
  V.pb(b);V.pb(a);V.pb(pivot);
  for(int i=1;i<=K;++i){
    if(i!=a&&i!=b&&i!=pivot)V.pb(i);
  }
  int p=query(V);
  return k-p;
}

void solve(int N) {
  K=N;
  for(int i=1;i+2<=N;++i){
    firsts[i]=find_diff(i,i+1,i+2);
    // cerr<<"F "<<i<<' '<<firsts[i]<<'\n';
  }
  for(int i=2;i+1<=N;++i){
    mids[i]=find_diff(i,i-1,i+1);
    // cerr<<"M "<<i<<' '<<mids[i]<<'\n';
  }

  vi ans;
  for(int i=1;i<=N;++i)for(int j=1;j<=N;++j){
    if(i==j)continue; 
    ans.clear();
    ans.pb(i);
    ans.pb(j);
    bool fail=0;
    while(SZ(ans)<N){
      // cerr<<"Length "<<SZ(ans)<<'\n';
      int lastdif=abs(ans[SZ(ans)-1] - ans[SZ(ans)-2]);
      // cerr<<lastdif<<'\n';
      int otdiff=abs(firsts[SZ(ans)-1]+lastdif);
      // cout<<otdiff<<'\n';
      int stdiff=abs(mids[SZ(ans)]+lastdif);
      // cout<<stdiff<<'\n';
      int a=ans[SZ(ans)-2];
      int b=ans[SZ(ans)-1];
      if(otdiff == stdiff+lastdif){
        if(a>b)ans.pb(a-otdiff);
        else ans.pb(a+otdiff);
      }else if(stdiff == otdiff+lastdif){
        // closer to first one
        if(a>b)ans.pb(a+otdiff);
        else ans.pb(a-otdiff);
      }else if(otdiff + stdiff == lastdif){
        if(a>b)ans.pb(a-otdiff);
        else ans.pb(a+otdiff);
      }else{
        fail=1;break;
      }
    }
    for(auto i:ans)if(i>N||i<1)fail=1;
    if(!fail){
      memset(R,0,sizeof(R));
      for(auto i:ans){
        if(R[i])fail=1;
        R[i]=1;
      }
    }
    // cerr<<fail<<'\n';
    if(fail==0){answer(ans);return;}
  }

  
  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]
   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]
   fscanf(stdin, "%d", &N);
   ~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 7.9714350000000005 / 15
• Subtask 2: 18.600015000000003 / 35
• Subtask 3: 26.571450000000002 / 50