QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#131864#5128. Dividing DNA mshcherba#AC ✓91ms3640kbC++17985b2023-07-28 17:04:522023-07-28 17:04:56

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-28 17:04:56]
  • 评测
  • 测评结果:AC
  • 用时:91ms
  • 内存:3640kb
  • [2023-07-28 17:04:52]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FILL(a, b) memset(a, b, sizeof(a))

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

bool ask(int i, int j) {
	cout << "? " << i << " " << j << endl;
	string res;
	cin >> res;
	return res == "present";
} 

int main()
{
	//ios::sync_with_stdio(false);
	//cin.tie(0);	
	int n;
	cin >> n;
	vector<int> f(n);
	int ptr = 0;
	FOR(i, 0, n) {
		ptr = max(ptr, i + 1);
		while (ptr <= n && ask(i, ptr)) {
			ptr++;
		}
		f[i] = ptr;
	}
	vector<int> dp(n + 1);
	dp[n] = 0;
	RFOR(i, n, 0) {
		dp[i] = dp[i + 1];
		if (f[i] <= n) {
			dp[i] = max(dp[i], dp[f[i]] + 1);
		}
	}
	cout << "! " << dp[0] << endl;
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3448kb

input:

1
absent

output:

? 0 1
! 1

result:

ok Used 1 queries

Test #2:

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

input:

5
present
absent
present
absent
present
present
absent
absent
present

output:

? 0 1
? 0 2
? 1 2
? 1 3
? 2 3
? 2 4
? 2 5
? 3 5
? 4 5
! 2

result:

ok Used 9 queries

Test #3:

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

input:

20
present
present
present
present
present
present
absent
absent
absent
present
present
absent
absent
absent
absent
absent
absent
present
absent
absent
present
present
present
present
absent
absent
absent
present
present
absent
absent
absent
present
absent
present
present

output:

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

result:

ok Used 36 queries

Test #4:

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

input:

30
present
present
present
present
present
present
present
present
present
present
present
present
present
absent
absent
absent
absent
absent
absent
absent
absent
present
present
present
present
present
present
present
absent
absent
absent
absent
absent
absent
absent
absent
present
absent
present
pr...

output:

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

result:

ok Used 47 queries

Test #5:

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

input:

40
present
present
present
present
present
present
present
present
present
present
absent
absent
absent
absent
present
present
present
present
present
present
present
present
present
present
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
present
absent
absent
absent
present
pr...

output:

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

result:

ok Used 68 queries

Test #6:

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

input:

50
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
prese...

output:

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

result:

ok Used 82 queries

Test #7:

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

input:

60
present
present
present
present
absent
absent
absent
present
present
present
present
present
present
absent
absent
absent
absent
absent
absent
present
present
absent
absent
absent
present
present
present
present
absent
absent
absent
present
present
absent
absent
present
present
present
absent
abs...

output:

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

result:

ok Used 113 queries

Test #8:

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

input:

33
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
abse...

output:

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

result:

ok Used 65 queries

Test #9:

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

input:

54
present
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
pres...

output:

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

result:

ok Used 106 queries

Test #10:

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

input:

43
present
present
present
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
pre...

output:

? 0 1
? 0 2
? 0 3
? 0 4
? 0 5
? 1 5
? 1 6
? 2 6
? 2 7
? 3 7
? 3 8
? 4 8
? 4 9
? 5 9
? 5 10
? 6 10
? 6 11
? 7 11
? 7 12
? 8 12
? 8 13
? 9 13
? 9 14
? 10 14
? 10 15
? 11 15
? 11 16
? 12 16
? 12 17
? 13 17
? 13 18
? 14 18
? 14 19
? 15 19
? 15 20
? 16 20
? 16 21
? 17 21
? 17 22
? 18 22
? 18 23
? 19 23
?...

result:

ok Used 82 queries

Test #11:

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

input:

55
present
present
present
present
present
present
present
present
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
...

output:

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

result:

ok Used 101 queries

Test #12:

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

input:

60
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
absent
present
absent
present
absent
present
absent
present
absen...

output:

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

result:

ok Used 91 queries

Test #13:

score: 0
Accepted
time: 91ms
memory: 3600kb

input:

10000
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
a...

output:

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

result:

ok Used 19999 queries

Test #14:

score: 0
Accepted
time: 58ms
memory: 3576kb

input:

10000
present
present
absent
present
absent
present
present
absent
absent
present
absent
present
present
absent
absent
present
absent
present
present
absent
absent
present
absent
present
present
absent
absent
present
absent
present
present
absent
absent
present
absent
present
present
absent
absent
p...

output:

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

result:

ok Used 19998 queries

Test #15:

score: 0
Accepted
time: 51ms
memory: 3520kb

input:

10000
present
present
present
present
absent
present
present
absent
absent
present
present
present
absent
absent
absent
present
present
absent
absent
present
present
present
absent
absent
absent
present
present
absent
absent
present
present
present
absent
absent
absent
present
present
absent
absent
...

output:

? 0 1
? 0 2
? 0 3
? 0 4
? 0 5
? 1 5
? 1 6
? 1 7
? 2 7
? 3 7
? 3 8
? 3 9
? 3 10
? 4 10
? 5 10
? 6 10
? 6 11
? 6 12
? 7 12
? 8 12
? 8 13
? 8 14
? 8 15
? 9 15
? 10 15
? 11 15
? 11 16
? 11 17
? 12 17
? 13 17
? 13 18
? 13 19
? 13 20
? 14 20
? 15 20
? 16 20
? 16 21
? 16 22
? 17 22
? 18 22
? 18 23
? 18 24
...

result:

ok Used 19996 queries

Test #16:

score: 0
Accepted
time: 79ms
memory: 3640kb

input:

10000
present
present
present
present
present
present
present
present
present
absent
present
present
present
present
present
absent
absent
absent
absent
absent
present
present
present
present
present
absent
absent
absent
absent
absent
present
present
present
present
present
absent
absent
absent
abse...

output:

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

result:

ok Used 19991 queries

Test #17:

score: 0
Accepted
time: 51ms
memory: 3524kb

input:

10000
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
presen...

output:

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

result:

ok Used 19901 queries

Test #18:

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

input:

10000
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
...

output:

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

result:

ok Used 10000 queries

Test #19:

score: 0
Accepted
time: 24ms
memory: 3580kb

input:

10000
present
absent
present
present
absent
absent
present
present
absent
absent
present
present
absent
absent
present
present
absent
absent
present
present
absent
absent
present
present
absent
absent
present
present
absent
absent
present
present
absent
absent
present
present
absent
absent
present
p...

output:

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

result:

ok Used 19999 queries

Test #20:

score: 0
Accepted
time: 58ms
memory: 3584kb

input:

10000
present
present
absent
present
present
present
absent
absent
absent
present
present
present
absent
absent
absent
present
present
present
absent
absent
absent
present
present
present
absent
absent
absent
present
present
present
absent
absent
absent
present
present
present
absent
absent
absent
p...

output:

? 0 1
? 0 2
? 0 3
? 1 3
? 1 4
? 1 5
? 1 6
? 2 6
? 3 6
? 4 6
? 4 7
? 4 8
? 4 9
? 5 9
? 6 9
? 7 9
? 7 10
? 7 11
? 7 12
? 8 12
? 9 12
? 10 12
? 10 13
? 10 14
? 10 15
? 11 15
? 12 15
? 13 15
? 13 16
? 13 17
? 13 18
? 14 18
? 15 18
? 16 18
? 16 19
? 16 20
? 16 21
? 17 21
? 18 21
? 19 21
? 19 22
? 19 23
?...

result:

ok Used 19997 queries

Test #21:

score: 0
Accepted
time: 34ms
memory: 3520kb

input:

10000
present
present
present
present
present
present
present
present
present
absent
present
present
present
present
present
present
present
present
present
present
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
present
present
present
present
present
present
present
present
p...

output:

? 0 1
? 0 2
? 0 3
? 0 4
? 0 5
? 0 6
? 0 7
? 0 8
? 0 9
? 0 10
? 1 10
? 1 11
? 1 12
? 1 13
? 1 14
? 1 15
? 1 16
? 1 17
? 1 18
? 1 19
? 1 20
? 2 20
? 3 20
? 4 20
? 5 20
? 6 20
? 7 20
? 8 20
? 9 20
? 10 20
? 11 20
? 11 21
? 11 22
? 11 23
? 11 24
? 11 25
? 11 26
? 11 27
? 11 28
? 11 29
? 11 30
? 12 30
? ...

result:

ok Used 19991 queries

Test #22:

score: 0
Accepted
time: 51ms
memory: 3584kb

input:

10000
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
presen...

output:

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

result:

ok Used 19901 queries

Test #23:

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

input:

10000
present
present
present
present
absent
absent
absent
absent
absent
present
present
present
present
present
absent
absent
present
absent
absent
absent
absent
present
present
present
present
absent
absent
absent
absent
present
present
present
present
present
absent
absent
present
absent
absent
a...

output:

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

result:

ok Used 19496 queries

Test #24:

score: 0
Accepted
time: 63ms
memory: 3640kb

input:

10000
present
present
present
present
absent
absent
absent
present
present
present
present
absent
absent
absent
present
absent
absent
absent
absent
present
present
absent
absent
present
absent
absent
present
present
present
present
absent
absent
absent
absent
present
present
present
present
absent
a...

output:

? 0 1
? 0 2
? 0 3
? 0 4
? 0 5
? 1 5
? 2 5
? 3 5
? 3 6
? 3 7
? 3 8
? 3 9
? 4 9
? 5 9
? 6 9
? 6 10
? 7 10
? 8 10
? 9 10
? 10 11
? 10 12
? 10 13
? 11 13
? 12 13
? 12 14
? 13 14
? 14 15
? 14 16
? 14 17
? 14 18
? 14 19
? 15 19
? 16 19
? 17 19
? 18 19
? 18 20
? 18 21
? 18 22
? 18 23
? 19 23
? 20 23
? 21 2...

result:

ok Used 19435 queries

Test #25:

score: 0
Accepted
time: 56ms
memory: 3536kb

input:

10000
present
present
present
present
present
present
present
absent
absent
absent
absent
absent
absent
present
present
present
present
present
present
present
present
present
absent
absent
absent
present
present
absent
absent
absent
absent
absent
present
present
present
present
absent
absent
absent...

output:

? 0 1
? 0 2
? 0 3
? 0 4
? 0 5
? 0 6
? 0 7
? 0 8
? 1 8
? 2 8
? 3 8
? 4 8
? 5 8
? 6 8
? 6 9
? 6 10
? 6 11
? 6 12
? 6 13
? 6 14
? 6 15
? 6 16
? 6 17
? 7 17
? 8 17
? 9 17
? 9 18
? 9 19
? 10 19
? 11 19
? 12 19
? 13 19
? 14 19
? 14 20
? 14 21
? 14 22
? 14 23
? 15 23
? 16 23
? 17 23
? 18 23
? 19 23
? 19 24...

result:

ok Used 19787 queries

Test #26:

score: 0
Accepted
time: 36ms
memory: 3580kb

input:

10000
present
present
present
present
present
present
present
present
present
present
present
present
present
present
absent
absent
absent
absent
absent
absent
absent
absent
present
present
present
present
present
present
present
present
present
present
present
present
present
absent
absent
absent
a...

output:

? 0 1
? 0 2
? 0 3
? 0 4
? 0 5
? 0 6
? 0 7
? 0 8
? 0 9
? 0 10
? 0 11
? 0 12
? 0 13
? 0 14
? 0 15
? 1 15
? 2 15
? 3 15
? 4 15
? 5 15
? 6 15
? 7 15
? 8 15
? 8 16
? 8 17
? 8 18
? 8 19
? 8 20
? 8 21
? 8 22
? 8 23
? 8 24
? 8 25
? 8 26
? 8 27
? 8 28
? 9 28
? 10 28
? 11 28
? 12 28
? 13 28
? 14 28
? 15 28
? ...

result:

ok Used 19756 queries

Test #27:

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

input:

10000
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
presen...

output:

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

result:

ok Used 19619 queries

Test #28:

score: 0
Accepted
time: 84ms
memory: 3580kb

input:

10000
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
presen...

output:

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

result:

ok Used 19286 queries

Test #29:

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

input:

10
present
present
present
present
present
present
present
present
present
present

output:

? 0 1
? 0 2
? 0 3
? 0 4
? 0 5
? 0 6
? 0 7
? 0 8
? 0 9
? 0 10
! 0

result:

ok Used 10 queries

Test #30:

score: 0
Accepted
time: 49ms
memory: 3528kb

input:

10000
present
present
present
absent
absent
absent
absent
present
present
present
present
present
absent
absent
present
present
absent
absent
present
present
absent
absent
absent
absent
absent
absent
present
present
present
present
present
absent
absent
present
present
absent
absent
absent
absent
ab...

output:

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

result:

ok Used 19549 queries

Test #31:

score: 0
Accepted
time: 34ms
memory: 3512kb

input:

10000
present
present
present
absent
absent
absent
present
present
present
absent
absent
absent
absent
present
present
present
present
absent
absent
absent
absent
present
present
absent
absent
absent
present
present
present
present
present
absent
absent
present
absent
absent
absent
present
present
p...

output:

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

result:

ok Used 19645 queries

Test #32:

score: 0
Accepted
time: 61ms
memory: 3524kb

input:

10000
present
present
present
present
absent
absent
absent
present
present
present
present
present
present
present
present
absent
absent
absent
absent
absent
absent
absent
present
present
present
present
present
absent
absent
absent
absent
absent
present
present
present
present
present
present
absen...

output:

? 0 1
? 0 2
? 0 3
? 0 4
? 0 5
? 1 5
? 2 5
? 3 5
? 3 6
? 3 7
? 3 8
? 3 9
? 3 10
? 3 11
? 3 12
? 3 13
? 4 13
? 5 13
? 6 13
? 7 13
? 8 13
? 9 13
? 10 13
? 10 14
? 10 15
? 10 16
? 10 17
? 10 18
? 11 18
? 12 18
? 13 18
? 14 18
? 15 18
? 15 19
? 15 20
? 15 21
? 15 22
? 15 23
? 15 24
? 16 24
? 17 24
? 18 2...

result:

ok Used 19715 queries

Test #33:

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

input:

10000
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
presen...

output:

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

result:

ok Used 19627 queries

Test #34:

score: 0
Accepted
time: 43ms
memory: 3528kb

input:

10000
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
presen...

output:

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

result:

ok Used 19494 queries

Test #35:

score: 0
Accepted
time: 28ms
memory: 3520kb

input:

10000
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
absent
absent
absent
absent
absent
absent
absent
absent
absent
absent
...

output:

? 0 1
? 0 2
? 0 3
? 0 4
? 0 5
? 0 6
? 0 7
? 0 8
? 0 9
? 0 10
? 0 11
? 0 12
? 0 13
? 0 14
? 0 15
? 0 16
? 0 17
? 0 18
? 0 19
? 0 20
? 0 21
? 0 22
? 0 23
? 0 24
? 0 25
? 0 26
? 0 27
? 0 28
? 0 29
? 1 29
? 2 29
? 3 29
? 4 29
? 5 29
? 6 29
? 7 29
? 8 29
? 9 29
? 10 29
? 11 29
? 12 29
? 13 29
? 14 29
? 1...

result:

ok Used 19501 queries

Test #36:

score: 0
Accepted
time: 20ms
memory: 3576kb

input:

10000
present
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
p...

output:

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

result:

ok Used 19998 queries

Test #37:

score: 0
Accepted
time: 25ms
memory: 3576kb

input:

10000
present
present
present
present
present
present
present
present
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
prese...

output:

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

result:

ok Used 19991 queries

Test #38:

score: 0
Accepted
time: 31ms
memory: 3516kb

input:

10000
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
absent
present
a...

output:

? 0 1
? 0 2
? 0 3
? 0 4
? 0 5
? 0 6
? 0 7
? 0 8
? 0 9
? 0 10
? 0 11
? 0 12
? 0 13
? 0 14
? 0 15
? 0 16
? 0 17
? 1 17
? 1 18
? 2 18
? 2 19
? 3 19
? 3 20
? 4 20
? 4 21
? 5 21
? 5 22
? 6 22
? 6 23
? 7 23
? 7 24
? 8 24
? 8 25
? 9 25
? 9 26
? 10 26
? 10 27
? 11 27
? 11 28
? 12 28
? 12 29
? 13 29
? 13 30
...

result:

ok Used 19984 queries

Test #39:

score: 0
Accepted
time: 50ms
memory: 3596kb

input:

10000
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
presen...

output:

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

result:

ok Used 19402 queries

Test #40:

score: 0
Accepted
time: 31ms
memory: 3584kb

input:

10000
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
presen...

output:

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

result:

ok Used 15051 queries

Test #41:

score: 0
Accepted
time: 54ms
memory: 3580kb

input:

10000
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
presen...

output:

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

result:

ok Used 15001 queries

Test #42:

score: 0
Accepted
time: 31ms
memory: 3600kb

input:

10000
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
presen...

output:

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

result:

ok Used 15000 queries

Test #43:

score: 0
Accepted
time: 68ms
memory: 3640kb

input:

10000
present
present
present
present
present
present
present
present
absent
absent
absent
absent
absent
present
present
present
present
present
absent
absent
absent
absent
present
absent
absent
present
absent
present
present
present
present
present
present
absent
absent
absent
present
absent
absent...

output:

? 0 1
? 0 2
? 0 3
? 0 4
? 0 5
? 0 6
? 0 7
? 0 8
? 0 9
? 1 9
? 2 9
? 3 9
? 4 9
? 5 9
? 5 10
? 5 11
? 5 12
? 5 13
? 5 14
? 6 14
? 7 14
? 8 14
? 9 14
? 9 15
? 10 15
? 11 15
? 11 16
? 12 16
? 12 17
? 12 18
? 12 19
? 12 20
? 12 21
? 12 22
? 13 22
? 14 22
? 15 22
? 15 23
? 16 23
? 17 23
? 18 23
? 19 23
? ...

result:

ok Used 19868 queries

Test #44:

score: 0
Accepted
time: 47ms
memory: 3640kb

input:

10000
present
present
present
present
present
present
present
present
present
present
present
present
present
present
absent
absent
absent
absent
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
pr...

output:

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

result:

ok Used 19977 queries

Test #45:

score: 0
Accepted
time: 51ms
memory: 3528kb

input:

10000
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
absent
absent
absent
absent
absent
present
present
present
present
present
present
present
present
present
present
absent
present
present
present
present
present
present
pres...

output:

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

result:

ok Used 19941 queries

Test #46:

score: 0
Accepted
time: 72ms
memory: 3488kb

input:

10000
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
present
presen...

output:

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

result:

ok Used 19728 queries

Test #47:

score: 0
Accepted
time: 37ms
memory: 3592kb

input:

10000
present
absent
absent
present
absent
absent
present
absent
absent
absent
absent
absent
present
absent
absent
present
absent
absent
present
absent
absent
present
absent
absent
present
absent
absent
present
absent
absent
present
absent
absent
absent
present
absent
absent
absent
absent
absent
pre...

output:

? 0 1
? 0 2
? 1 2
? 2 3
? 2 4
? 3 4
? 4 5
? 4 6
? 5 6
? 6 7
? 7 8
? 8 9
? 9 10
? 9 11
? 10 11
? 11 12
? 11 13
? 12 13
? 13 14
? 13 15
? 14 15
? 15 16
? 15 17
? 16 17
? 17 18
? 17 19
? 18 19
? 19 20
? 19 21
? 20 21
? 21 22
? 21 23
? 22 23
? 23 24
? 24 25
? 24 26
? 25 26
? 26 27
? 27 28
? 28 29
? 29 3...

result:

ok Used 13331 queries

Test #48:

score: 0
Accepted
time: 52ms
memory: 3516kb

input:

10000
present
absent
absent
present
absent
absent
present
absent
absent
absent
present
absent
absent
absent
absent
present
present
absent
absent
present
absent
absent
present
absent
absent
present
absent
present
present
absent
absent
absent
present
present
present
absent
absent
absent
present
presen...

output:

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

result:

ok Used 17618 queries