QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#740622#9432. PermutationAllenJYLWA 359ms3684kbC++144.3kb2024-11-13 10:46:252024-11-13 10:46:26

Judging History

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

  • [2024-11-13 10:46:26]
  • 评测
  • 测评结果:WA
  • 用时:359ms
  • 内存:3684kb
  • [2024-11-13 10:46:25]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

// #define int long long
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
#define all(_array) (_array).begin(),(_array).end()
#define msp(_array) memset(_array,0x3f,sizeof _array)
#define ms0(_array) memset(_array,0,sizeof _array)
#define msn(_array) memset(_array,-1,sizeof _array)
#define mc(_tar,_array) memcpy(_tar,_array,sizeof _tar)
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define TAK cout<<"TAK"<<endl
#define NIE cout<<"NIE"<<endl
#define OK cerr<<"OK"<<endl
#define pii pair<int,int>
// #define endl '\n'

bool bg_memory;
mt19937 rnd(time(0));
int Case=1;
const int mod=1e9+7;
const int inf=2147483647;
const int bs=233;
const double eps=1e-6;
const int N=1e3+7,M=1e5+7;

template<class _t1,class _t2>inline void cmax(_t1 &a,_t2 b){a=a<b?b:a;}
template<class _t1,class _t2>inline void cmin(_t1 &a,_t2 b){a=a>b?b:a;}
inline int qp(int a,int b,int p=mod){int res=1;while(b){if(b&1)res=1ll*res*a%p;a=1ll*a*a%p;b>>=1;}return res;}
inline int sqrt(int x,int r){int l=0,ans=0;while(l<=r){if(1ll*mid*mid<=x) ans=mid,l=mid+1;else r=mid-1;}return ans;}

int n;
int id[N];
int ans[N],qu[N];
vector<int> v;
int ask(int l,int r,int a,int b){
    for(int i=1;i<=n;i++) qu[i]=b;
    for(int i=l;i<=r;i++) qu[id[i]]=a;
    cout<<"0 ";
    for(int i=1;i<=n;i++) cout<<qu[i]<<" ";
    cout<<endl;
    int tmp;
    cin>>tmp;
    return tmp;
}
void solve(int l,int r,vector<int> v,int tmp){
    // cout<<l<<" "<<r<<endl;
    // for(int i:v) cout<<i<<" ";
    // cout<<endl<<tmp<<endl;
    if(l==r) return ans[id[l]]=v.back(),void();
    vector<int> L,R;
    if(tmp){
        for(int i:v){
            if(L.size()==mid-l+1){
                R.push_back(i);
            }else if(R.size()==r-mid){
                L.push_back(i);
            }else{
                int res=ask(l,mid,i,tmp);
                if(res==2) L.push_back(i);
                else R.push_back(i);
            }
        }
    }else{
        vector<int> unk;
        unk.push_back(1);
        int fl=0;
        for(int i:v){
            if(i==1) continue;
            if(L.size()==mid-l+1){
                R.push_back(i);
                continue;
            }else if(R.size()==r-mid){
                L.push_back(i);
                continue;
            }
            if(!fl){
                int res=ask(l,mid,i,1);
                if(res==2){
                    L.push_back(i);
                    fl=2;
                    for(int j:unk) R.push_back(j);
                    unk.clear();
                }else if(res==0){
                    R.push_back(i);
                    fl=1;
                    for(int j:unk) L.push_back(j);
                    unk.clear();
                }else{
                    unk.push_back(i);
                }
            }else if(fl==1){
                int res=ask(l,mid,i,1);
                if(res==1){
                    L.push_back(i);
                }else{
                    R.push_back(i);
                }
            }else{
                int res=ask(l,mid,i,1);
                if(res==2){
                    L.push_back(i);
                }else{
                    R.push_back(i);
                }
            }
        }
    }
    solve(l,mid,L,R.back());
    solve(mid+1,r,R,L.back());
}

void Main(){
    
    cin>>n;
    for(int i=1;i<=n;i++) id[i]=i,v.push_back(i);
    shuffle(id+1,id+n+1,rnd);
    solve(1,n,v,0);
    cout<<"1 ";
    for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
    
    return;
}
string RdFile="";
bool en_memory;

signed main(){
    auto bg_clock=chrono::high_resolution_clock::now();
#ifdef ONLINE_JUDGE
    // freopen((RdFile+".in").c_str(),"r",stdin);
    // freopen((RdFile+".out").c_str(),"w",stdout);
#endif
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    // cin>>Case;
    while(Case--) Main();
    auto en_clock=chrono::high_resolution_clock::now();
    auto duration_clock=chrono::duration_cast<chrono::microseconds>(en_clock-bg_clock);
    double duration_count=duration_clock.count()*0.001;
    double memory_used=(&en_memory-&bg_memory)/1024.0/1024;
    // cerr<<"Time:"<<duration_count<<"ms"<<endl;
    // cerr<<"Memory: "<<memory_used<<"MB"<<endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
0
0
2
2
2
2

output:

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

result:

ok Accepted

Test #2:

score: -100
Wrong Answer
time: 359ms
memory: 3576kb

input:

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

output:

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

result:

wrong answer More than 6666 quries