CSES - Putka Open 2025 – 4/5

Submission details
Task:	Huippualkio
Sender:	Yytsi
Submission time:	2025-11-09 13:16:53 +0200
Language:	C++ (C++20)
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	16
#2	ACCEPTED	42
#3	ACCEPTED	42

Test results
test	verdict	time	group
#1	ACCEPTED	0.02 s	1, 2, 3	details
#2	ACCEPTED	0.02 s	1, 2, 3	details
#3	ACCEPTED	0.02 s	1, 2, 3	details
#4	ACCEPTED	0.02 s	1, 2, 3	details
#5	ACCEPTED	0.02 s	1, 2, 3	details
#6	ACCEPTED	0.02 s	1, 2, 3	details
#7	ACCEPTED	0.02 s	1, 2, 3	details
#8	ACCEPTED	0.02 s	1, 2, 3	details
#9	ACCEPTED	0.02 s	2, 3	details
#10	ACCEPTED	0.02 s	2, 3	details
#11	ACCEPTED	0.02 s	2, 3	details
#12	ACCEPTED	0.02 s	2, 3	details
#13	ACCEPTED	0.02 s	2, 3	details
#14	ACCEPTED	0.02 s	2, 3	details
#15	ACCEPTED	0.19 s	3	details
#16	ACCEPTED	0.18 s	3	details
#17	ACCEPTED	0.25 s	3	details
#18	ACCEPTED	0.48 s	3	details
#19	ACCEPTED	0.37 s	3	details
#20	ACCEPTED	0.37 s	3	details
#21	ACCEPTED	0.02 s	1, 2, 3	details
#22	ACCEPTED	0.02 s	2, 3	details
#23	ACCEPTED	0.40 s	3	details
#24	ACCEPTED	0.02 s	1, 2, 3	details
#25	ACCEPTED	0.02 s	1, 2, 3	details
#26	ACCEPTED	0.02 s	1, 2, 3	details
#27	ACCEPTED	0.02 s	1, 2, 3	details
#28	ACCEPTED	0.02 s	1, 2, 3	details
#29	ACCEPTED	0.02 s	1, 2, 3	details
#30	ACCEPTED	0.02 s	1, 2, 3	details
#31	ACCEPTED	0.02 s	1, 2, 3	details

Code

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

#define N 1010101
int n;
int known[N];

void solve(int pos) {
  cout << "! " << pos << endl;
  exit(0);
}

void check(int x) {

}

void triv(int x) {
  for (int i = max(1,x-3); i <= min(n, x+3); i++) {
    if (known[i-1] == -1 || known[i] == -1 || known[i+1] == -1) continue;
    if (known[i-1] <= known[i] && known[i] >= known[i+1]) solve(i);  
  }
}

int q(int pos) {
  if (known[pos] != -1) return known[pos];
  cout << "? " << pos << endl;
  int res = 0;
  cin>>res;
  known[pos] = res;
  triv(pos);
  return res;
}

void f(int l, int r) {
  int m = r - l + 1;
  if (m == 1) solve(1);
  if (m == 2) {
    int a = q(l);
    int b = q(r);
    solve(a >= b ? 1 : 2);
  } else if (m == 3) {
    int a = q(l);
    int b = q(l+1);
    if (a >= b) solve(l);
    int c = q(r);
    if (b <= c) solve(r);
    solve(l+1);
  }

  int mid = (r + l) / 2;
  int x = q(mid);
  int w = q(mid-1);
  // check if left space has ans
  if (w >= x) {
    f(l, mid);
  } else f(mid, r);
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  

  fill(known, known + N, -1);

  cin>>n;

  // both neighbouring ends from [1,n] are lower
  known[0] = -2;
  known[n+1] = -2;

  f(1, n);  
}

Test details

Test 1 (public)

Group: 1, 2, 3

Verdict: ACCEPTED

input
`8 5 2 4 1 3 3 2 4` view save

correct output
(empty)

user output
`8 ? 4 1 ? 3 4 ...` view save

Error:

1 1 100 0

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
`1 1` view save

correct output
(empty)

user output
`1 ! 1` view save

Error:

1 1 100 0

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
`50 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
(empty)

user output
`50 ? 25 1 ? 24 1 ...` view save

Error:

1 1 100 0

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
`50 2 1 2 2 2 2 1 1 1 1 2 1 1 2 2 ...` view save

correct output
(empty)

user output
`50 ? 25 2 ? 24 1 ...` view save

Error:

1 1 100 0

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
`50 657 448 315 782 966 983 560 32...` view save

correct output
(empty)

user output
`50 ? 25 841 ? 24 639 ...` view save

Error:

1 1 100 0

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
`50 541463939 624015614 406717194 ...` view save

correct output
(empty)

user output
`50 ? 25 722672739 ? 24 919585635 ...` view save

Error:

1 1 100 0

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
`50 1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

correct output
(empty)

user output
`50 ? 25 25 ? 24 24 ...` view save

Error:

1 1 100 0

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
`50 50 49 48 47 46 45 44 43 42 41 ...` view save

correct output
(empty)

user output
`50 ? 25 26 ? 24 27 ...` view save

Error:

1 1 100 0

Test 9

Group: 2, 3

Verdict: ACCEPTED

input
`100 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
(empty)

user output
`100 ? 50 1 ? 49 1 ...` view save

Error:

1 1 100 0

Test 10

Group: 2, 3

Verdict: ACCEPTED

input
`100 1 2 2 1 2 1 1 2 2 1 2 2 1 1 2 ...` view save

correct output
(empty)

user output
`100 ? 50 1 ? 49 1 ...` view save

Error:

1 1 100 0

Test 11

Group: 2, 3

Verdict: ACCEPTED

input
`100 401 388 765 398 183 79 268 339...` view save

correct output
(empty)

user output
`100 ? 50 786 ? 49 469 ...` view save

Error:

1 1 100 0

Test 12

Group: 2, 3

Verdict: ACCEPTED

input
`100 34030354 571736161 659501910 9...` view save

correct output
(empty)

user output
`100 ? 50 14405655 ? 49 822261941 ...` view save

Error:

1 1 100 0

Test 13

Group: 2, 3

Verdict: ACCEPTED

input
`100 1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

correct output
(empty)

user output
`100 ? 50 50 ? 49 49 ...` view save

Error:

1 1 100 0

Test 14

Group: 2, 3

Verdict: ACCEPTED

input
`100 100 99 98 97 96 95 94 93 92 91...` view save

correct output
(empty)

user output
`100 ? 50 51 ? 49 52 ...` view save

Error:

1 1 100 0

Test 15

Group: 3

Verdict: ACCEPTED

input
`1000000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
(empty)

user output
`1000000 ? 500000 1 ? 499999 1 ...` view save

Error:

1 1 100 0

Test 16

Group: 3

Verdict: ACCEPTED

input
`1000000 2 1 1 2 2 2 2 1 2 1 1 1 1 1 1 ...` view save

correct output
(empty)

user output
`1000000 ? 500000 2 ? 499999 1 ...` view save

Error:

1 1 100 0

Test 17

Group: 3

Verdict: ACCEPTED

input
`1000000 338 877 986 388 699 868 559 99...` view save

correct output
(empty)

user output
`1000000 ? 500000 320 ? 499999 49 ...` view save

Error:

1 1 100 0

Test 18

Group: 3

Verdict: ACCEPTED

input
`1000000 301892461 304390263 250772451 ...` view save

correct output
(empty)

user output
`1000000 ? 500000 166777359 ? 499999 426386515 ...` view save

Error:

1 1 100 0

Test 19

Group: 3

Verdict: ACCEPTED

input
`1000000 1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

correct output
(empty)

user output
`1000000 ? 500000 500000 ? 499999 499999 ...` view save

Error:

1 1 100 0

Test 20

Group: 3

Verdict: ACCEPTED

input
`1000000 1000000 999999 999998 999997 9...` view save

correct output
(empty)

user output
`1000000 ? 500000 500001 ? 499999 500002 ...` view save

Error:

1 1 100 0

Test 21

Group: 1, 2, 3

Verdict: ACCEPTED

input
`50 1000000 1000001 1000002 100000...` view save

correct output
(empty)

user output
`50 ? 25 1000024 ? 24 1000023 ...` view save

Error:

1 1 100 0

Test 22

Group: 2, 3

Verdict: ACCEPTED

input
`100 1000000 1000001 1000002 100000...` view save

correct output
(empty)

user output
`100 ? 50 1000009 ? 49 1000010 ...` view save

Error:

1 1 100 0

Test 23

Group: 3

Verdict: ACCEPTED

input
`1000000 1000000 1000001 1000002 100000...` view save

correct output
(empty)

user output
`1000000 ? 500000 1247825 ? 499999 1247826 ...` view save

Error:

1 1 100 0

Test 24

Group: 1, 2, 3

Verdict: ACCEPTED

input
`1 1000000000` view save

correct output
(empty)

user output
`1 ! 1` view save

Error:

1 1 100 0

Test 25

Group: 1, 2, 3

Verdict: ACCEPTED

input
`2 1 1` view save

correct output
(empty)

user output
`2 ? 1 1 ? 2 1 ...` view save

Error:

1 1 100 0

Test 26

Group: 1, 2, 3

Verdict: ACCEPTED

input
`2 1 2` view save

correct output
(empty)

user output
`2 ? 1 1 ? 2 2 ...` view save

Error:

1 1 100 0

Test 27

Group: 1, 2, 3

Verdict: ACCEPTED

input
`2 2 1` view save

correct output
(empty)

user output
`2 ? 1 2 ? 2 1 ...` view save

Error:

1 1 100 0

Test 28

Group: 1, 2, 3

Verdict: ACCEPTED

input
`3 1 1 1` view save

correct output
(empty)

user output
`3 ? 1 1 ? 2 1 ...` view save

Error:

1 1 100 0

Test 29

Group: 1, 2, 3

Verdict: ACCEPTED

input
`3 1 1 2` view save

correct output
(empty)

user output
`3 ? 1 1 ? 2 1 ...` view save

Error:

1 1 100 0

Test 30

Group: 1, 2, 3

Verdict: ACCEPTED

input
`3 1 2 1` view save

correct output
(empty)

user output
`3 ? 1 1 ? 2 2 ...` view save

Error:

1 1 100 0

Test 31

Group: 1, 2, 3

Verdict: ACCEPTED

input
`3 2 1 1` view save

correct output
(empty)

user output
`3 ? 1 2 ? 2 1 ...` view save

Error:

1 1 100 0

Putka Open 2025 – 4/5

Huippualkio

Code

Test details

Test 1 (public)

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Tasks

Submissions (Yytsi)