QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#736514#5128. Dividing DNA nicksms#AC ✓47ms3932kbC++17994b2024-11-12 11:31:272024-11-12 11:31:27

Judging History

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

  • [2024-11-12 11:31:27]
  • 评测
  • 测评结果:AC
  • 用时:47ms
  • 内存:3932kb
  • [2024-11-12 11:31:27]
  • 提交

answer

/**
 *      Author:  Nicholas Winschel
 *      Created: 11.11.2024 22:16:13
**/

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())
#define each(a,b) for (auto &a : b)

int main() {
  cin.tie(0)->sync_with_stdio(0); // initialize fast I/O

  int n; cin >> n;
  vi rb(n), dp(n);
  for (int i = 0; i < n; i++) {
    if (i) rb[i] = rb[i-1];
    if (rb[i] < i) rb[i]=i;
    while (1) {
      if (rb[i] == n) break;
      cout << "? " << i << " " << rb[i]+1 << endl;
      string s; cin >> s;
      if (s == "absent") break;
      rb[i]++;
    }
  }
  for (int i = n-1; i >= 0; --i) {
    if (i < n-1) dp[i] = dp[i+1];
    if (rb[i] < n) {
      dp[i] = max(dp[i], 1+((rb[i]<n-1)?dp[rb[i]+1]:0));
    }
  }
  cout << "! " << dp[0] << "\n";

  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1
absent

output:

? 0 1
! 1

result:

ok Used 1 queries

Test #2:

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

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: 3584kb

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: 1ms
memory: 3556kb

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: 1ms
memory: 3564kb

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: 1ms
memory: 3584kb

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: 3564kb

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: 1ms
memory: 3560kb

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: 1ms
memory: 3860kb

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: 0ms
memory: 3852kb

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: 1ms
memory: 3844kb

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: 1ms
memory: 3556kb

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: 25ms
memory: 3896kb

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: 12ms
memory: 3572kb

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: 18ms
memory: 3624kb

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: 37ms
memory: 3632kb

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: 24ms
memory: 3700kb

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: 4ms
memory: 3920kb

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: 32ms
memory: 3688kb

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: 33ms
memory: 3848kb

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: 18ms
memory: 3724kb

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: 16ms
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 19901 queries

Test #23:

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

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: 14ms
memory: 3628kb

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: 17ms
memory: 3656kb

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: 26ms
memory: 3624kb

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: 29ms
memory: 3856kb

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: 17ms
memory: 3632kb

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: 1ms
memory: 3604kb

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: 47ms
memory: 3676kb

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: 24ms
memory: 3656kb

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: 38ms
memory: 3684kb

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: 37ms
memory: 3636kb

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: 10ms
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 19494 queries

Test #35:

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

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: 17ms
memory: 3864kb

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: 34ms
memory: 3672kb

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: 29ms
memory: 3852kb

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: 19ms
memory: 3696kb

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: 18ms
memory: 3688kb

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: 13ms
memory: 3692kb

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: 6ms
memory: 3624kb

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: 13ms
memory: 3628kb

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: 24ms
memory: 3920kb

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: 7ms
memory: 3692kb

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: 19ms
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 19728 queries

Test #47:

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

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: 29ms
memory: 3932kb

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