QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#740949#9432. PermutationL_WaveRE 1ms3772kbC++201.8kb2024-11-13 12:37:032024-11-13 12:37:10

Judging History

你现在查看的是最新测评结果

  • [2024-11-13 12:37:10]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3772kb
  • [2024-11-13 12:37:03]
  • 提交

answer

// Problem: K. Permutation
// Author: XZC(L_Wave)
// Language: Cpp/G++20
// Contest: Hydro
// URL: http://www.nfls.com.cn:10611/p/16530?tid=67333207920ee48161ddde7f
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Create Time: not 2024-11-13 11:43:37, but 1926-08-17 11:45:14
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i <= i##ABRACADABRA; i++)
#define drep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i >= i##ABRACADABRA; i--)
using namespace std;
using ll = long long;

int n,res[1000010];

int ask(int x,int y,int piv){
  putchar(48);
  rep(i,1,piv)printf(" %d",x);
  rep(i,piv+1,n)printf(" %d",y);
  puts(""),fflush(stdout);
  scanf("%d",&piv);
  return piv;
}

void solve(int l,int r,vector<int>V){
  if (l==r)return void(res[l]=V[0]);
  vector<int>L,R,U;
  int mid=(l+r)>>1;
  for (auto v:V){
    if (!U.size()){
      U.push_back(v);
      continue;
    }
    if (L.size()){
      int x=ask(L[0],v,mid);
      if (x==2)R.push_back(v);
      else L.push_back(v);
    }else if (R.size()){
      int x=ask(v,R[0],mid);
      if (x==2)L.push_back(v);
      else R.push_back(v);
    }else{
      int x=ask(v,U[0],mid);
      if (x==1)continue;
      if (!x){
        for (auto t:U)L.push_back(t);
        U.clear();
        R.push_back(v);
      }else{
        for (auto t:U)R.push_back(t);
        U.clear();
        L.push_back(v);
      }
    }
  }
  if ((int)L.size()+(int)U.size()==mid-l+1)
    for (auto t:U)L.push_back(t);
  else
    for (auto t:U)R.push_back(t);
  solve(l,mid,L),solve(mid+1,r,R);
}

int main() {
  scanf("%d",&n);
  vector<int>V;
  rep(i,1,n)V.push_back(i);
  solve(1,n,V);
  putchar(49);
  rep(i,1,n)printf(" %d",res[i]);
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3772kb

input:

5
2
1
2
2
2
0

output:

0 2 2 2 1 1
0 2 2 2 4 4
0 2 2 2 5 5
0 4 4 2 2 2
0 3 4 4 4 4
0 5 5 5 5 1
1 3 4 2 1 5

result:

ok Accepted

Test #2:

score: -100
Runtime Error

input:

1000
0
1
2
1
2
2
1
2
1
2
2
1
1
2
1
1
1
1
1
1
2
2
2
2
2
1
2
2
2
1
2
1
1
1
1
2
1
1
1
1
2
2
1
2
2
1
1
2
1
2
2
1
2
2
1
2
1
1
2
2
2
1
1
1
1
1
2
2
2
1
2
2
2
2
2
1
1
1
1
2
2
1
2
2
2
2
2
1
1
2
1
2
1
1
2
2
1
2
1
1
1
1
1
2
1
1
1
2
1
1
2
1
2
1
2
1
1
1
1
1
2
1
1
1
1
2
1
1
2
1
1
1
2
2
2
1
2
1
2
2
2
2
1
2
1
2
2
2...

output:

0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

result: