QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#812663#9783. Duloc Networkucup-team135#WA 1ms3564kbC++202.5kb2024-12-13 17:43:422024-12-13 17:43:43

Judging History

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

  • [2024-12-13 17:43:43]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3564kb
  • [2024-12-13 17:43:42]
  • 提交

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;
}

















详细

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'