oj.uz

Submission #259609

# Submission time Handle Problem Language Result Execution time Memory
259609 2020-08-08T04:10:42 Z dvdg6566 Secret Permutation (RMI19_permutation) C++14
26.5714 / 100
 44 ms 256 KB 
#include "permutation.h"
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
const int MAXN = 256;
#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

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.971435 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 256 KB Partially correct
2 Partially correct 0 ms 256 KB Partially correct
3 Partially correct 0 ms 256 KB Partially correct
4 Partially correct 1 ms 256 KB Partially correct
5 Partially correct 1 ms 256 KB Partially correct
6 Partially correct 0 ms 256 KB Partially correct

Subtask #2
18.600015 / 35.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 256 KB Partially correct
2 Partially correct 0 ms 256 KB Partially correct
3 Partially correct 0 ms 256 KB Partially correct
4 Partially correct 1 ms 256 KB Partially correct
5 Partially correct 1 ms 256 KB Partially correct
6 Partially correct 0 ms 256 KB Partially correct
7 Partially correct 3 ms 256 KB Partially correct
8 Partially correct 3 ms 256 KB Partially correct
9 Partially correct 3 ms 256 KB Partially correct
10 Partially correct 3 ms 256 KB Partially correct
11 Partially correct 3 ms 256 KB Partially correct
12 Partially correct 4 ms 256 KB Partially correct
13 Partially correct 3 ms 256 KB Partially correct
14 Partially correct 3 ms 256 KB Partially correct
15 Partially correct 4 ms 256 KB Partially correct
16 Partially correct 4 ms 256 KB Partially correct

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 256 KB Partially correct
2 Partially correct 0 ms 256 KB Partially correct
3 Partially correct 0 ms 256 KB Partially correct
4 Partially correct 1 ms 256 KB Partially correct
5 Partially correct 1 ms 256 KB Partially correct
6 Partially correct 0 ms 256 KB Partially correct
7 Partially correct 3 ms 256 KB Partially correct
8 Partially correct 3 ms 256 KB Partially correct
9 Partially correct 3 ms 256 KB Partially correct
10 Partially correct 3 ms 256 KB Partially correct
11 Partially correct 3 ms 256 KB Partially correct
12 Partially correct 4 ms 256 KB Partially correct
13 Partially correct 3 ms 256 KB Partially correct
14 Partially correct 3 ms 256 KB Partially correct
15 Partially correct 4 ms 256 KB Partially correct
16 Partially correct 4 ms 256 KB Partially correct
17 Incorrect 44 ms 256 KB Output isn't correct
18 Halted 0 ms 0 KB -