QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#672869 | #9432. Permutation | huazai676 | ML | 0ms | 0kb | C++17 | 1.8kb | 2024-10-24 19:36:29 | 2024-10-24 19:36:29 |
answer
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<random>
using namespace std;
const int N=1010;
mt19937 rd(102937);
int n;
int p[N];
int Q(int l,int r,int x,int y)
{
int mid=(l+r)/2;
cout<<"0 ";
for(int i=1;i<=mid;i++) cout<<x<<' ';
for(int i=mid+1;i<=n;i++) cout<<y<<' ';
cout<<endl;
int res;
cin>>res;
return res;
}
void solve(int l,int r,vector<int> s)
{
if(l==r)
{
p[l]=s[0];
return;
}
int mid=(l+r)/2;
shuffle(s.begin(),s.end(),rd);
vector<int> ls,rs,tmp;
for(int i=0;i<s.size();)
{
if(i<s.size()-1)
{
int x=s[i],y=s[i+1];
int k=Q(l,r,x,y);
if(k==1)
{
tmp.push_back(x);
i+=1;
}
else if(k==0)
{
tmp.push_back(x);
for(int t:tmp) ls.push_back(t);
tmp.clear();
rs.push_back(y);
i+=2;
}
else
{
tmp.push_back(x);
for(int t:tmp) rs.push_back(t);
tmp.clear();
ls.push_back(y);
i+=2;
}
}
else
{
int x=s[i];
tmp.push_back(x);
if(ls.size()<rs.size()) for(int t:tmp) ls.push_back(t);
else for(int t:tmp) rs.push_back(t);
}
}
solve(l,mid,ls),solve(mid+1,r,rs);
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
vector<int> s;
for(int i=1;i<=n;i++) s.push_back(i);
solve(1,n,s);
cout<<"1 ";
for(int i=1;i<=n;i++) cout<<p[i]<<' ';
cout<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Memory Limit Exceeded
input:
5 1 1 2
output:
0 3 3 3 2 2 0 2 2 2 4 4 0 4 4 4 5 5