QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#672869#9432. Permutationhuazai676ML 0ms0kbC++171.8kb2024-10-24 19:36:292024-10-24 19:36:29

Judging History

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

  • [2024-10-24 19:36:29]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [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 

result: