oj.uz

답안 #1054008

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1054008 2024-08-12T04:00:08 Z huutuan Secret Permutation (RMI19_permutation) C++14
0 / 100
 0 ms 344 KB 
#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);
   }
   int x1=mx+1, x2=n-mx;
   int y1=x1+diff, y2=x2+diff;
   int id=cand[0];
   vector<int> vis(n+1);
   if (cand.size()==2){
      ans[x]=x1; ans[y]=y1;
      vis[x1]=vis[y1]=1;
   }else{
      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(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 (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

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
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -