QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#777048#9783. Duloc Networkucup-team3670#WA 1ms3832kbC++202.1kb2024-11-23 22:28:042024-11-23 22:28:04

Judging History

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

  • [2024-11-23 22:28:04]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3832kb
  • [2024-11-23 22:28:04]
  • 提交

answer

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
#define sz(a) (int)((a).size())

using namespace std;

typedef long long li;

//const int N = 205;
typedef string bs;

string operator |(const string &a, const string &b){
	string c(a.size(), '0');
	forn(i, a.size()) c[i] = max(a[i], b[i]);
	return c;
}

int n;
map<bs, int> memo;

int ask(bs cur){
	int cnt = count(cur.begin(), cur.end(), '1');
	if (cnt == 0 || cnt == n)
		return memo[cur] = 0;
	if (cnt > n - cnt || (cnt == n - cnt && cur[0] == '1')){
		forn(i, n) cur[i] ^= '0' ^ '1';
	}
	if (memo.count(cur))
		return memo[cur];
	cout << "? ";
	forn(i, n) cout << cur[i];
	cout << endl;
	int x;
	cin >> x;
	memo[cur] = x;
	return x;
}

int aske(bs a, bs b){
	return (ask(a) + ask(b) - ask(a | b)) / 2;
}

vector<bs> comp;
vector<int> rk, p;

int getp(int a){
	return a == p[a] ? a : p[a] = getp(p[a]);
}

void unite(int a, int b){
	a = getp(a), b = getp(b);
	if (a == b) return;
	if (rk[a] < rk[b]) swap(a, b);
	rk[a] += rk[b];
	p[b] = a;
	comp[a] = comp[a] | comp[b];
}

int main(){
	//cin.tie(0);
	//ios::sync_with_stdio(false);
	cin >> n;
	vector<bs> cur(n, string(n, '0'));
	forn(i, n) cur[i][i] = '1';
	while (sz(cur) > 1){		
		p.resize(sz(cur));
		iota(p.begin(), p.end(), 0);
		rk.assign(sz(cur), 1);
		comp = cur;
		
		forn(i, sz(cur)){
			auto a = cur[i];
			cur.erase(cur.begin() + i);
			
			auto collect = [&](int l, int r){
				bs tmp(n, '0');
				fore(i, l, r) tmp = tmp | cur[i];
				return tmp;
			};
			
			int l = 0, r = sz(cur);
			auto tmp = collect(l, r);
			int val = aske(a, tmp);
			if (val == 0){
				cout << "! " << 0 << endl;
				return 0;
			}
			while (l < r - 1){
				int m = (l + r) / 2;
				auto nw = collect(l, m);
				if (aske(a, nw) == 0)
					l = m;
				else
					r = m;
			}
			unite(i, l < i ? l : (l + 1));
			cur.insert(cur.begin() + i, a);
		}
		
		cur.clear();
		forn(i, sz(comp)) if (getp(i) == i)
			cur.push_back(comp[i]);
	}
	
	cout << "! " << 1 << endl;
}

详细

Test #1:

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

input:

4
1
3
1
2
2
2
2

output:

? 1000
? 0100
? 0011
? 0010
? 0101
? 0110
? 0001
! 1

result:

ok Correct answer with 7 queries.

Test #2:

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

input:

2
0

output:

? 01
! 0

result:

ok Correct answer with 1 queries.

Test #3:

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

input:

4
1
3
1
2
2
2
2

output:

? 1000
? 0100
? 0011
? 0010
? 0101
? 0110
? 0001
! 1

result:

ok Correct answer with 7 queries.

Test #4:

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

input:

2
0

output:

? 01
! 0

result:

ok Correct answer with 1 queries.

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3632kb

input:

50
3
14
19
14
15
8
11
4
7
3
6
3
6
1
16
16
12
5
6
1
2
4
5
1
15
14
12
13
6
7
1
2
3
3
1
15
15
12
7
2
4
16
14
11
7
6
1
2
2
3
16
18
19
15
17
9
11
4
8
3
7
3
15
19
18
5
8
1
4
2
3
1
16
15
12
5
1
2
2
3
1
15
14
13
6
2
4
2
16
20
10
12
11
12
4
6
2
3
15
20
13
13
7
3
15
19
16
11
2
5
2
4
2
16
17
14
9
6
5
16
16
15
...

output:

? 10000000000000000000000000000000000000000000000000
? 01111111111111111111111110000000000000000000000000
? 00000000000000000000000001111111111111111111111111
? 01111111111110000000000000000000000000000000000000
? 11111111111110000000000000000000000000000000000000
? 011111100000000000000000000000000...

result:

wrong answer Wrong answer.