QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#776225 | #9783. Duloc Network | ucup-team3282# | TL | 0ms | 0kb | C++14 | 1.8kb | 2024-11-23 17:56:58 | 2024-11-23 17:56:58 |
answer
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<ctime>
#include<random>
using namespace std;
mt19937 a(114514);
int f[1000050];
string base,s;
int n;
int cnt=0;
int query(vector<int>s1){
cnt++;
if(cnt>3500){
for(int i=1;i>=1;i++);
}
s=base;
for(auto x:s1){
s[x-1]='1';
}
cout<<"? "<<s<<endl;
int x;cin>>x;
return x;
}
vector<int>mer(vector<int>a,vector<int>b){
for(auto x:b){
a.push_back(x);
}
return a;
}
int solveb(vector<int>q,int num,vector<int>s){
// cout<<"now testing: ";
// for(auto x:s){
// cout<<x<<"-";
// }cout<<endl;
int sz=s.size();
if(sz==1){
if(query(s)+num>query(mer(q,s)))return s[0];
return -1;
}
vector<int>s1;
for(int i=0;i<sz/2;i++){
s1.push_back(s[i]);
}
if(query(s1)+num>query(mer(q,s1))){
return solveb(q,num,s1);
}else{
vector<int>s2;
for(int i=sz/2;i<sz;i++){
s2.push_back(s[i]);
}
return solveb(q,num,s2);
}
}
vector<int>lg;
bool vis[1000050];
bool solve(){
bool flag=0;
for(int i=1;i<=n;i++){
vis[i]=0;
}
vector<int>nw;
for(auto x:lg){
vis[x]=1;
}
// cout<<endl;
for(int i=1;i<=n;i++){
if(vis[i]==0){
// cout<<i<<"/";
nw.push_back(i);
}
}
// cout<<endl;
int p=solveb(lg,query(lg),nw);
// return 0;
if(p==-1)
return 0;
else{
lg.push_back(p);
return 1;
}
}
int main(){
cin>>n;
int mx=1;
for(int i=1;i<=n;i++){
base=base+'0';
}
lg.push_back(1);
while(solve());
if(lg.size()==n)cout<<"! 1"<<endl;
else cout<<"! 0"<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
4 1 3 2 3 2 2 2 1 2 1 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
? 1000 ? 0100 ? 1100 ? 0100 ? 1100 ? 1100 ? 0010 ? 1110 ? 0010 ? 1110 ? 1110 ? 0001 ? 1111 ? 1111 ? 0000 ? 1111 ? 0000 ? 1111 ? 0000 ? 1111 ? 0000 ? 1111 ? 0000 ? 1111 ? 0000 ? 1111 ? 0000 ? 1111 ? 0000 ? 1111 ? 0000 ? 1111 ? 0000 ? 1111 ? 0000 ? 1111 ? 0000 ? 1111 ? 0000 ? 1111 ? 0000 ? 1111 ? 0000...