QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#777229#9783. Duloc Networkucup-team3670#TL 6ms3952kbC++201.9kb2024-11-23 23:54:422024-11-23 23:54:43

Judging History

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

  • [2024-11-23 23:54:43]
  • 评测
  • 测评结果:TL
  • 用时:6ms
  • 内存:3952kb
  • [2024-11-23 23:54:42]
  • 提交

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;

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

/*string operator !(const string &a){
	string c(a.size(), '0');
	forn(i, a.size()) c[i] = a[i] ^ '0' ^ '1';
	return c;
}*/

int n;
map<bs, int> memo;

int queries;

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

int ask2(bs a, bs b){
	return ask(a) + ask(b) != ask(a | b);
}

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

mt19937 rnd(42);

int main(){
	//cin.tie(0);
	//ios::sync_with_stdio(false);
	cin >> n;
	comp.assign(n, string(n, '0'));
	forn(i, n) comp[i][i] = '1';
	rk.assign(n, 1);
	p.resize(n);
	iota(p.begin(), p.end(), 0);
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 0);
	while (sz(ord) > 1){
		shuffle(ord.begin(), ord.end(), rnd);
		bool ok = false;
		fore(i, 1, sz(ord)) if (ask2(comp[getp(ord[0])], comp[getp(ord[i])])){
			unite(ord[0], ord[i]);
			ok = true;
		}
		if (!ok){
			cout << "! " << 0 << endl;
			return 0;
		}
		vector<int> nord;
		forn(i, sz(ord)) if (ord[i] == getp(ord[i]))
			nord.push_back(ord[i]);
		ord = nord;
	}
	cout << "! " << 1 << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
3
2
2
2
1
1

output:

? 0100
? 0001
? 0101
? 0010
? 0111
? 1000
! 1

result:

ok Correct answer with 6 queries.

Test #2:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

2
0
0

output:

? 01
? 10
! 0

result:

ok Correct answer with 2 queries.

Test #3:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

4
3
2
2
2
1
1

output:

? 0100
? 0001
? 0101
? 0010
? 0111
? 1000
! 1

result:

ok Correct answer with 6 queries.

Test #4:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

2
0
0

output:

? 01
? 10
! 0

result:

ok Correct answer with 2 queries.

Test #5:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

50
1
1
2
3
4
2
3
4
5
1
2
4
5
2
3
1
2
1
2
4
5
2
3
3
4
1
2
3
4
1
2
1
2
1
2
3
4
2
3
3
4
3
4
3
4
2
3
3
4
4
4
1
5
4
8
1
5
2
6
1
5
2
6
1
4
1
5
2
6
3
7
1
4
3
6
2
8
3
9
2
8
1
7
1
7
6
11
3
10
2
11
1
12
2
12
2
14
4
11
3
5
4
6
7
5
5
5
7
6
5
5
7
8
8
9
10
12
13
13
15
11
12
11
11
12
10
12
9
10
10
9
8
8
7
7
7
6
7
...

output:

? 00000000000000000000000000000000000000001000000000
? 00000000000000000000000010000000000000000000000000
? 00000000000000000000000010000000000000001000000000
? 00000000000000000000000000000000000000000010000000
? 00000000000000000000000000000000000000001010000000
? 000000000000000000000000000001000...

result:

ok Correct answer with 180 queries.

Test #6:

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

input:

50
9
10
17
11
24
15
31
8
33
16
37
10
38
11
39
16
40
10
39
9
38
10
37
10
36
6
35
9
34
9
33
8
32
8
31
10
30
11
29
10
29
13
28
14
27
15
26
10
25
10
24
14
23
10
22
5
21
11
20
11
19
13
18
13
17
12
16
8
15
15
14
8
13
8
12
10
11
10
10
9
9
13
8
7
7
7
6
10
5
15
4
6
3
9
2
10
1
10

output:

? 00000000000000000000000000000000000000001000000000
? 00000000000000000000000010000000000000000000000000
? 00000000000000000000000010000000000000001000000000
? 00000000000000000000000000000000000000000010000000
? 00000000000000000000000010000000000000001010000000
? 000000000000000000000000000001000...

result:

ok Correct answer with 98 queries.

Test #7:

score: 0
Accepted
time: 2ms
memory: 3644kb

input:

50
2
2
4
1
3
3
4
1
5
3
7
2
6
1
5
1
5
1
5
4
7
3
10
4
11
4
10
1
11
3
13
1
11
1
11
3
13
3
13
1
9
1
10
1
8
1
9
1
9
1
9
1
9
1
8
2
10
2
8
1
7
1
8
3
10
4
8
3
8
2
10
1
9
1
9
2
10
2
7
3
8
3
7
5
7
4
9
2
10
3
13
1
11
3
12
1
13
5
11
4
7
4
2
5
5
3
5
4
5
4
3
3
2
4
3
3
3
3
1
10
11
11
11
9
10
10
9
8
9
9
2
4
3
2
4
2...

output:

? 00000000000000000000000000000000000000001000000000
? 00000000000000000000000010000000000000000000000000
? 00000000000000000000000010000000000000001000000000
? 00000000000000000000000000000000000000000010000000
? 00000000000000000000000000000000000000001010000000
? 000000000000000000000000000001000...

result:

ok Correct answer with 204 queries.

Test #8:

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

input:

50
11
9
17
10
24
4
24
12
26
5
26
11
28
4
29
9
30
11
31
7
32
8
34
7
34
8
33
9
32
9
32
8
31
8
30
8
29
10
28
2
27
10
27
9
27
8
26
12
25
10
24
8
23
12
22
5
21
8
20
8
19
5
18
7
17
10
16
9
15
7
14
8
13
7
12
6
11
9
10
5
9
14
8
8
7
6
6
7
5
13
4
9
3
4
2
10
1
8

output:

? 00000000000000000000000000000000000000001000000000
? 00000000000000000000000010000000000000000000000000
? 00000000000000000000000010000000000000001000000000
? 00000000000000000000000000000000000000000010000000
? 00000000000000000000000010000000000000001010000000
? 000000000000000000000000000001000...

result:

ok Correct answer with 98 queries.

Test #9:

score: 0
Accepted
time: 3ms
memory: 3608kb

input:

50
1
2
3
1
2
3
4
1
2
2
3
1
2
2
3
1
2
2
3
1
2
2
3
1
2
1
2
1
2
2
3
1
2
1
2
2
3
1
2
3
4
2
3
3
4
1
2
1
2
3
4
1
2
1
2
1
2
1
2
1
2
1
2
2
3
2
3
5
6
3
2
1
1
2
3
1
2
1
2
1
2
1
2
1
0
3
3
2
2
1
1
1
1
1
1
3
3
1
1
2
2
4
2
2
3
3
2
2
3
3
5
5
4
4
2
3
3
4
6
5
5
6
6
7
7
6
8
6
6
4
5
5
5
5
4
6
5
3
3
5
6
4
5
3
4
2
5
3
3...

output:

? 00000000000000000000000000000000000000001000000000
? 00000000000000000000000010000000000000000000000000
? 00000000000000000000000010000000000000001000000000
? 00000000000000000000000000000000000000000010000000
? 00000000000000000000000000000000000000001010000000
? 000000000000000000000000000001000...

result:

ok Correct answer with 343 queries.

Test #10:

score: 0
Accepted
time: 3ms
memory: 3664kb

input:

100
1
2
3
4
5
2
3
1
2
3
4
1
2
1
2
2
3
1
2
2
3
1
2
1
2
2
3
2
3
1
2
1
2
3
4
2
3
3
4
1
2
1
2
1
2
3
2
1
3
3
5
4
6
1
3
1
3
3
5
3
5
2
4
1
3
1
3
2
4
1
3
1
3
2
4
1
3
3
5
2
4
5
7
1
3
3
5
1
3
1
3
2
4
1
3
1
3
1
3
4
6
3
5
2
4
1
3
4
4
1
5
1
5
3
7
2
6
1
5
1
5
1
5
3
7
1
5
2
6
2
6
1
5
1
5
1
5
1
5
2
6
1
5
1
5
1
5
2
...

output:

? 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000
? 0000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000
? 00000000000000000000000000000000000000000000000000000000000000000000000000100000000000000100...

result:

ok Correct answer with 805 queries.

Test #11:

score: 0
Accepted
time: 2ms
memory: 3664kb

input:

100
8
5
12
6
17
10
27
5
20
5
21
8
24
16
35
8
40
16
48
10
49
13
58
8
57
12
59
10
63
13
65
12
66
8
66
8
66
6
66
11
65
10
65
8
66
10
66
15
66
7
66
8
66
6
65
11
65
15
67
12
68
7
67
13
67
11
66
5
66
8
65
9
64
8
63
6
62
11
61
7
60
5
59
9
58
13
57
8
56
16
55
9
54
11
53
6
52
5
51
11
50
12
49
7
48
11
47
8
46...

output:

? 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000
? 0000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000
? 00000000000000000000000000000000000000000000000000000000000000000000000000100000000000000100...

result:

ok Correct answer with 199 queries.

Test #12:

score: 0
Accepted
time: 2ms
memory: 3624kb

input:

100
1
1
2
2
1
4
5
7
8
3
4
5
6
4
5
6
7
4
5
5
6
1
2
2
3
4
5
2
3
2
3
8
9
4
5
3
4
5
6
5
6
2
3
2
3
3
4
2
3
4
5
3
4
2
3
1
2
2
3
2
3
3
4
3
4
2
3
2
3
4
5
3
4
5
6
3
4
2
3
6
6
5
11
2
8
3
9
3
9
4
10
5
11
3
8
5
13
4
11
3
11
6
17
4
15
4
13
3
14
6
17
2
19
5
22
1
18
2
19
3
19
3
19
3
20
4
21
4
25
3
23
1
24
5
26
3
2...

output:

? 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000
? 0000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000
? 00000000000000000000000000000000000000000000000000000000000000000000000000100000000000000100...

result:

ok Correct answer with 274 queries.

Test #13:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

100
1
2
3
1
2
1
2
2
3
4
4
1
5
1
5
2
6
2
6
1
5
2
6
1
5
3
7
1
5
1
5
1
5
4
8
1
5
1
5
1
5
1
4
3
7
1
5
3
7
1
5
1
5
3
7
1
5
3
7
1
5
2
3
4
6
1
7
4
8
1
9
1
9
4
12
1
9
2
10
2
10
5
13
2
10
3
11
1
7
2
9
1
8
1
8
4
8
2
10
1
9
2
8
1
9
3
11
4
10
1
10
5
15
1
11
1
11
1
11
2
12
1
11
2
11
3
14
3
12
1
13
2
14
3
15
1
13...

output:

? 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000
? 0000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000
? 00000000000000000000000000000000000000000000000000000000000000000000000000100000000000000100...

result:

ok Correct answer with 503 queries.

Test #14:

score: 0
Accepted
time: 6ms
memory: 3712kb

input:

100
4
1
5
1
5
2
6
3
7
2
6
3
7
1
5
2
6
1
5
1
5
1
5
1
5
5
8
1
9
2
10
1
9
1
9
3
11
1
9
1
9
2
10
1
7
1
8
2
7
1
8
1
8
2
9
1
8
1
6
4
10
3
7
1
8
2
9
2
9
2
9
1
8
1
8
2
9
1
8
3
10
3
10
1
8
2
9
2
9
1
8
2
8
1
7
4
8
1
9
1
9
2
10
2
10
3
11
1
9
1
9
1
9
2
10
1
7
1
8
1
7
2
9
2
9
1
8
1
8
2
6
1
7
1
7
2
8
1
7
3
9
1
7
...

output:

? 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000
? 0000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000
? 00000000000000000000000000000000000000000000000000000000000000000000000000100000000000000100...

result:

ok Correct answer with 826 queries.

Test #15:

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

input:

150
2
3
5
6
8
5
7
2
4
3
5
2
4
1
3
1
3
5
7
1
3
6
8
1
3
2
4
4
6
2
4
4
6
3
5
1
3
2
4
3
5
2
4
2
4
1
3
3
5
2
4
1
2
3
5
3
5
3
5
7
8
4
12
2
10
2
10
4
12
4
12
5
13
3
11
1
9
3
11
1
9
2
10
4
12
2
10
4
11
4
14
2
13
4
14
2
16
3
16
2
17
3
20
3
20
3
19
2
21
3
21
1
22
1
22
1
21
2
23
3
23
1
24
1
24
2
25
2
24
3
27
3...

output:

? 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000
? 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000...

result:

ok Correct answer with 435 queries.

Test #16:

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

input:

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

output:

? 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000
? 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000...

result:

ok Correct answer with 414 queries.

Test #17:

score: 0
Accepted
time: 2ms
memory: 3632kb

input:

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

output:

? 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000
? 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000...

result:

ok Correct answer with 453 queries.

Test #18:

score: 0
Accepted
time: 4ms
memory: 3744kb

input:

150
3
5
8
2
5
3
6
4
7
3
6
2
5
2
5
1
4
3
6
3
4
2
6
3
7
2
6
1
5
6
10
2
6
1
5
4
8
5
9
1
5
3
7
3
7
4
8
2
6
1
5
1
5
1
5
3
7
2
6
3
7
2
6
6
10
2
5
1
6
1
6
2
5
3
7
5
11
8
19
1
12
3
13
1
14
3
16
3
15
3
18
3
16
3
18
7
25
1
19
4
22
4
22
3
19
2
20
4
24
4
20
5
19
2
20
3
21
2
20
1
21
3
22
1
23
4
25
2
27
8
30
3
33...

output:

? 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000
? 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000...

result:

ok Correct answer with 416 queries.

Test #19:

score: 0
Accepted
time: 0ms
memory: 3952kb

input:

150
2
3
5
4
6
2
4
3
5
5
7
1
3
1
1
3
4
2
3
1
2
1
2
4
5
3
4
1
2
2
3
1
2
1
2
2
3
2
3
2
3
4
5
1
2
1
2
1
2
2
3
2
3
1
2
1
2
1
2
1
2
1
2
1
2
3
4
3
4
2
3
1
2
1
2
2
3
1
2
1
2
2
3
2
3
1
2
1
2
1
2
3
4
2
3
1
2
2
3
3
4
1
2
2
3
3
4
3
4
1
2
1
2
1
2
1
2
2
3
1
2
2
3
2
3
1
2
2
3
2
3
2
3
3
4
1
2
1
2
3
4
3
4
2
3
3
4
2
...

output:

? 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000
? 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000...

result:

ok Correct answer with 1371 queries.

Test #20:

score: -100
Time Limit Exceeded

input:

200
2
1
3
2
4
2
4
2
4
2
4
1
2
1
3
1
3
2
4
1
3
2
4
1
3
1
3
1
3
3
2
2
4
1
3
1
3
2
4
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
2
4
1
3
1
3
2
4
1
3
1
3
2
4
1
3
4
6
1
3
4
6
1
3
1
3
1
3
1
3
1
3
1
3
4
6
2
4
4
6
1
3
1
3
2
4
1
3
4
6
1
3
3
5
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
2
4
1
3
3
5
1
3
1
3
2
4
2
...

output:

? 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result: