QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#741481 | #9432. Permutation | hotdogseller | TL | 1ms | 3776kb | C++14 | 1.9kb | 2024-11-13 14:28:31 | 2024-11-13 14:28:33 |
Judging History
answer
#include<bits/stdc++.h>
#define maxn 10005
#define INF 1e18
#define int long long
using namespace std;
inline int read(){
int lre=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-'){
f=-1;
}
c=getchar();
}
while(c>='0'&&c<='9'){
lre=(lre<<3)+(lre<<1)+(c-'0');
c=getchar();
}
return lre*f;
}
int n;
int arr[maxn],brr[maxn];
vector<int> v;//空闲位置集合
void del(int x){
for(int i=0;i+1<v.size();i++){
if(v[i]==x){
swap(v[i],v[i+1]);
}
}
if(v[v.size()-1]==x)v.pop_back();
}
bool okay(int x,int ind){
for(int i=1;i<=n;i++){
if(arr[i]!=0){
brr[i]=arr[i];
}else if(i<ind){
brr[i]=x-1;//[1,x-1]已知,x-1一定是错的
}else{
brr[i]=x;
}
}
printf("0 ");
for(int i=1;i<=n;i++){
printf("%lld ",brr[i]);
}
putchar('\n');
fflush(stdout);
int lre=read();
return lre>=x;
}
void solve(int x){
int l=0,r=v.size()-1,mid,res;
while(l<=r){
mid=l+r>>1;
//认为位置v[mid]是x
if(okay(x,v[mid])){
res=v[mid];
l=mid+1;
}else{
r=mid-1;
}
}
del(res);
arr[res]=x;
}
signed main(){
n=read();
for(int i=1;i<=n;i++){
v.push_back(i);
}
for(int i=1;i<=n;i++)brr[i]=2;
for(int i=1;i<=n;i++){
// cout<<"i="<<i<<"!"<<endl;
brr[i]=1;
printf("0 ");
for(int j=1;j<=n;j++){
printf("%lld ",brr[j]);
}
putchar('\n');
fflush(stdout);
int lre=read();
if(lre==2){
//这一位是1
arr[i]=1;
del(i);
}else if(lre==0){
//这一位是2
arr[i]=2;
del(i);
}
brr[i]=2;
}//确定1的位置
for(int i=3;i<n;i++){
solve(i);
}
arr[v[0]]=n;//最后剩下的位置一定是n
printf("1 ");
for(int i=1;i<=n;i++){
printf("%lld ",arr[i]);
}
putchar('\n');
fflush(stdout);
return 0;
}
/*
二分确定每一个位置
第一个?
0 6 4 2 3 1 5
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3776kb
input:
5 1 1 0 2 1 2 3 4 3
output:
0 1 2 2 2 2 0 2 1 2 2 2 0 2 2 1 2 2 0 2 2 2 1 2 0 2 2 2 2 1 0 2 3 2 1 3 0 3 3 2 1 3 0 3 4 2 1 4 0 3 3 2 1 4 1 3 4 2 1 5
result:
ok Accepted
Test #2:
score: -100
Time Limit Exceeded
input:
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
0 1 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 ...