mxqz 周六晚上的 CF G
  • 板块学术版
  • 楼主樱雪喵>w<
  • 当前回复11
  • 已保存回复11
  • 发布时间2023/11/28 19:53
  • 上次更新2023/11/28 21:52:05
查看原帖
mxqz 周六晚上的 CF G
234074
樱雪喵>w<楼主2023/11/28 19:53

一直 TLE on test 3,实在想不出来错在哪里。

能 assert 的感觉都 assert 了,手捏数据无果,有没有大佬给个 hack /kk

#include<bits/stdc++.h>
#define il inline
using namespace std;
il long long read()
{
    long long xr=0,F=1; char cr;
    while(cr=getchar(),cr<'0'||cr>'9') if(cr=='-') F=-1;
    while(cr>='0'&&cr<='9') 
        xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();
    return xr*F;
}
const int N=405;
int n,ans[N],vis[N];
set<int> s[N];
vector<int> Ans;
int Cnt;
il int ask(set<int> s)
{
    assert(s.size()==n);
    Cnt++;
    cout<<"? ";for(auto x:s) cout<<x<<" ";cout<<endl;
    return read();
}
il void get(set<int> &s)
{
    int tot=1;
    for(int i=n-s.size();i;i--) 
    {
        while(vis[tot]||s.find(tot)!=s.end()) tot++;
        // cout<<"??"<<tot<<endl;
        assert(tot<=n*n);
        s.insert(tot);
    }
    assert(s.size()==n);
}
il void solve()
{
    Cnt=0;
    n=read();
    for(int i=0;i<=n*n+1;i++) vis[i]=0,ans[i]=0,s[i].clear();
    Ans.clear();
    for(int i=1;i<=n;i++)
    {
        for(int j=(i-1)*n+1;j<=i*n;j++) s[i].insert(j);
        ans[i]=ask(s[i]),vis[ans[i]]=1;
    }
    for(int tot=n*n;tot>=2*n;tot--)
    {
        set<int> now;
        for(int i=1;i<=n;i++) now.insert(ans[i]);
        get(now); int x=ask(now),id=(x-1)/n+1;
        Ans.push_back(x);
        s[id].erase(x),get(s[id]);
        
        ans[id]=ask(s[id]),vis[ans[id]]=1;
        for(int i=1;i<=n;i++) if(i!=id) s[i].erase(ans[id]);
    }
    set<int> now;
    for(int i=1;i<=n;i++) now.insert(ans[i]);
    get(now);
    for(int tot=n-1;tot;tot--)
    {
        int x=ask(now); now.erase(x),get(now);
        Ans.push_back(x);
    }
    // for(int i=1;i<=n*n;i++) cout<<vis[i]<<" "; cout<<endl;
    
    for(auto x:now) if(vis[x]) Ans.push_back(x);
    cout<<"! ";for(auto x:Ans) cout<<x<<" "; cout<<endl;
    assert(Ans.size()==n*n-n+1);
    assert(Cnt<=2*n*n-2*n+1);
}
int main() {int T=read();while(T--) solve();return 0;}
/*
9 1 6 3 5 8 4 7 2
*/
2023/11/28 19:53
加载中...