QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#812663 | #9783. Duloc Network | ucup-team135# | WA | 1ms | 3564kb | C++20 | 2.5kb | 2024-12-13 17:43:42 | 2024-12-13 17:43:43 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <fstream>
#include <array>
#include <functional>
#include <stack>
#include <memory>
using namespace std;
#define int long long
const int p=998244353;
int po(int a,int b) {if(b==0) return 1; if(b==1) return a; if(b%2==0) {int u=po(a,b/2);return (u*1LL*u)%p;} else {int u=po(a,b-1);return (a*1LL*u)%p;}}
int inv(int x) {return po(x,p-2);}
mt19937 rnd;
#define app push_back
#define all(x) (x).begin(),(x).end()
#ifdef LOCAL
#define debug(...) [](auto...a){ ((cout << a << ' '), ...) << endl;}(#__VA_ARGS__, ":", __VA_ARGS__)
#define debugv(v) do {cout<< #v <<" : {"; for(int izxc=0;izxc<v.size();++izxc) {cout << v[izxc];if(izxc+1!=v.size()) cout << ","; }cout <<"}"<< endl;} while(0)
#else
#define debug(...)
#define debugv(v)
#endif
#define lob(a,x) lower_bound(all(a),x)
#define upb(a,x) upper_bound(all(a),x)
int n;
map<vector<int>,int> mem;
int que(vector<int> v)
{
sort(all(v));
if(mem.count(v)) return mem[v];
string s;for(int i=0;i<n;++i) s.app('0');
for(int x:v) {s[x]='1';}
cout<<"? "<<s<<endl;
int ans;cin>>ans;
mem[v]=ans;
return ans;
}
bool good(vector<vector<int> > v)
{
int s=0;
for(int i=0;i<v.size();++i)
{
s+=que(v[i]);
}
vector<int> u;for(vector<int> h:v) for(int h1:h) u.app(h1);
return que(u)!=s;
}
pair<vector<int>,vector<int> > go(vector<vector<int> > cur)
{
if(!good(cur)) {return {{},{}};}
if(cur.size()==2) {return {cur[0],cur[1]};}
while(true) {
vector<vector<int> > cur2;
for(int i=0;i<cur.size();++i)
{
if(rnd()%2) {cur2.app(cur[i]);}
}
if(good(cur2))
{
return go(cur2);
}
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
vector<vector<int> > cur;
for(int i=0;i<n;++i) {cur.app({i});}
while(true)
{
auto [v1,v2]=go(cur);
if(v1.empty() && v2.empty()) break;
cur.erase(find(all(cur),v1));cur.erase(find(all(cur),v2));
for(int &x:v2) {v1.app(x);}
cur.app(v1);
}
cout<<(cur.size()==1 ? "YES" : "NO")<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3564kb
input:
4 1 3 2 2 0 1 1 1
output:
? 1000 ? 0100 ? 0010 ? 0001 ? 1111 ? 0111 ? 0011 ? 1011 YES
result:
wrong answer format Expected '!' or '?', but found 'YES'