QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#741029 | #9432. Permutation | L_Wave | TL | 1ms | 4064kb | C++20 | 1.9kb | 2024-11-13 13:01:44 | 2024-11-13 13:01:45 |
Judging History
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 (!V.size())while (1);
if (l==r)return void(res[l]=V[0]);
vector<int>L,R,U;
int mid=(l+r)>>1;
for (auto v:V){
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{
if (!U.size()){
U.push_back(v);
continue;
}
int x=ask(v,U[0],mid);
if (x==1){
U.push_back(x);
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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4064kb
input:
5 2 1 1 2 2 1 0 0
output:
0 2 2 2 1 1 0 2 2 2 3 3 0 2 2 2 4 4 0 2 2 2 5 5 0 3 3 2 2 2 0 3 3 4 4 4 0 4 3 3 3 3 0 5 5 5 5 1 1 3 4 2 1 5
result:
ok Accepted
Test #2:
score: -100
Time Limit Exceeded
input:
1000 0 2 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...
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 ...