QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#594202#1464. Interactive Algorithmzhenjianuo2025TL 1ms3676kbC++142.2kb2024-09-27 20:14:412024-09-27 20:14:41

Judging History

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

  • [2024-09-27 20:14:41]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3676kb
  • [2024-09-27 20:14:41]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define piii tuple<int,int,int>
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#define fi first
#define se second
#define ins insert
#define it iterator
#define lb lower_bound
#define ub upper_bound
#define exc(exp) if(exp)continue;
#define ret(exp) if(exp)return;
#define stop(exp) if(exp)break;
#define quit(sth) {sth;return;}
#define let(var...) int var;tie(var)
#define siz(vec) ((int)((vec).size()))
#define all(vec) (vec).begin(),(vec).end()
#define unq(vec) sort(all(vec)),(vec).erase(unique(all(vec)),(vec).end())
#define deb(var) cerr<<#var<<'='<<(var)<<"; "
#define debl(var) cerr<<#var<<'='<<(var)<<";\n"
#define db double
#define ll long long
#define x1 ____
#define y1 _____
#define inf (long long)(1e18)
mt19937 gen(random_device{}());
bool Max(int &x,int y){if(x<y)return x=y,1;return 0;}
bool Min(int &x,int y){if(x>y)return x=y,1;return 0;}
const int mod=1e9+7;
void Add(int &x,int y){x=x+y<mod?x+y:x+y-mod;}
int add(int x,int y){return x+y<mod?x+y:x+y-mod;}
int fpm(int x,int y){
	int ans=1;for(;y;y>>=1,(x*=x)%=mod)if(y&1)(ans*=x)%=mod;return ans;
}

int n,p[510],e[510][510];
vector<int> g[510];
void dfs(int u,int fa){
    cout<<' '<<u;
    for(auto v:g[u]){
        exc(v==fa);dfs(v,u);
    }
    if(siz(g[u])==1)cout<<endl;
}
void work(){
    cin>>n;
    iota(p+1,p+n+1,1);
    while(1){
        shuffle(p+1,p+n+1,gen);
        cout<<'?';for(int i=1;i<=n;i++)cout<<' '<<p[i];cout<<endl;
        int x;cin>>x;
        if(x==0){
            for(int i=1;i<n;i++)
                e[p[i]][p[i+1]]=e[p[i+1]][p[i]]=1;
        }
        int cnt=0;
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)cnt+=!e[i][j];if(cnt==n-1)break;
    }
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(!e[i][j])g[i].pb(j),g[j].pb(i);
    cout<<'!';
    for(int i=1;i<=n;i++){
        if(siz(g[i])==1)quit(dfs(i,0));
    }
}
signed main(){
	ios::sync_with_stdio(0),
	cin.tie(0),cout.tie(0);
	int T=1;while(T--)work();
}
/*
 * CONTINUE, NON-STOPPING, FOR THE FAITH
 * START TYPING IF YOU DON'T KNOW WHAT TO DO
 * STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING
 */

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

? 3 1 5 2 4
? 3 2 1 4 5
? 4 5 3 2 1
? 5 4 3 2 1
? 5 1 3 4 2
? 4 5 3 2 1
? 4 5 3 2 1
? 1 5 2 3 4
? 2 3 4 5 1
? 3 4 5 1 2
? 1 4 2 3 5
? 4 3 1 5 2
? 4 5 1 2 3
? 2 3 1 5 4
? 4 1 2 3 5
? 1 2 5 3 4
? 5 2 4 3 1
? 2 3 1 5 4
? 3 2 5 4 1
? 3 2 4 1 5
? 4 5 2 3 1
? 5 4 1 2 3
? 1 4 2 3 5
? 3 5 1 2 4
? 1 4 5 2 3
...

result:

ok n=5, 44 queries

Test #2:

score: 0
Accepted
time: 1ms
memory: 3676kb

input:

2
1

output:

? 1 2
! 1 2


result:

ok n=2, 1 queries

Test #3:

score: -100
Time Limit Exceeded

input:

3
2
2
2
1
1
1
2
1
1
1
1
2
1
1
2
2
1
1
1
2
1
1
1
2
1
1
1
2
1
1
1
2
1
2
2
1
1
1
2
1
1
1
1
1
1
2
1
2
1
2
1
1
2
1
2
1
1
2
1
1
1
1
1
2
1
2
1
1
1
1
2
1
2
2
1
1
1
1
1
1
2
1
1
1
1
1
1
2
2
1
2
2
2
1
1
1
1
1
2
2
1
1
1
1
1
1
2
1
2
2
2
1
1
1
1
1
1
2
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
1
2
2
1
1
1
1
1
1
1
2
...

output:

? 1 2 3
? 3 2 1
? 3 2 1
? 1 3 2
? 2 3 1
? 2 3 1
? 1 2 3
? 2 1 3
? 3 1 2
? 1 3 2
? 2 1 3
? 1 2 3
? 3 1 2
? 3 1 2
? 1 2 3
? 1 2 3
? 1 3 2
? 2 3 1
? 3 1 2
? 1 2 3
? 3 1 2
? 3 1 2
? 3 1 2
? 1 2 3
? 3 1 2
? 3 1 2
? 2 1 3
? 1 2 3
? 1 3 2
? 1 3 2
? 2 1 3
? 1 2 3
? 2 3 1
? 3 2 1
? 3 2 1
? 2 1 3
? 2 3 1
? 1 ...

result: