CSES - Putka Open 2025 – 4/5

Submission details
Task:	Huippualkio
Sender:	jlaire
Submission time:	2025-11-07 19:37:47 +0200
Language:	C++ (C++17)
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.01 s	1, 2, 3	details
#3	ACCEPTED	0.02 s	1, 2, 3	details
#4	ACCEPTED	0.01 s	1, 2, 3	details
#5	ACCEPTED	0.01 s	1, 2, 3	details
#6	ACCEPTED	0.01 s	1, 2, 3	details
#7	ACCEPTED	0.01 s	1, 2, 3	details
#8	ACCEPTED	0.02 s	1, 2, 3	details
#9	ACCEPTED	0.01 s	2, 3	details
#10	ACCEPTED	0.02 s	2, 3	details
#11	ACCEPTED	0.01 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.18 s	3	details
#16	ACCEPTED	0.19 s	3	details
#17	ACCEPTED	0.25 s	3	details
#18	ACCEPTED	0.48 s	3	details
#19	ACCEPTED	0.36 s	3	details
#20	ACCEPTED	0.36 s	3	details
#21	ACCEPTED	0.01 s	1, 2, 3	details
#22	ACCEPTED	0.02 s	2, 3	details
#23	ACCEPTED	0.40 s	3	details
#24	ACCEPTED	0.01 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.01 s	1, 2, 3	details
#28	ACCEPTED	0.01 s	1, 2, 3	details
#29	ACCEPTED	0.01 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 <algorithm>
#include <cassert>
#include <cstdlib>
#include <functional>
#include <iostream>
#include <map>
using namespace std;
using Q = function<int(int)>;

int query_io(int pos) {
    cout << "? " << pos << endl;
    int x; cin>>x;
    return x;
}

bool lmax(int pos, Q q) {
    return q(pos) >= max(q(pos-1), q(pos+1));
}

int solve_brute(int L, int R, Q q) {
    for (int i=L+1; i<R; i++)
        if (lmax(i,q)) return i;
    return lmax(L,q) ? L : R;
}

int solve(int L, int R, Q q) {
    if (L==R) return L;
    if (R-L<=5) {
        return solve_brute(L,R,q);
    }
    int M = L+(R-L)/2;
    if (q(M+1)>=q(M)) return solve(M,R,q);
    return solve(L,M,q);
}

int solve(int N, Q q0) {
    if (N==1) return 1;
    map<int,int> cache;
    Q q = [&](int pos) {
        if (pos<1 || pos>N) return -1;
        if (!cache.count(pos)) cache[pos] = q0(pos);
        return cache[pos];
    };
    if (q(1)>=q(2)) return 1;
    if (q(N)>=q(N-1)) return N;
    return solve(1, N, q);
}

int main() {
    int n; cin>>n;
    int ans = solve(n, query_io);
    cout << "! " << ans << endl;
}

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 ? 1 5 ? 2 2 ...` 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 ? 1 1 ? 2 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 ? 1 2 ? 2 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 ? 1 657 ? 2 448 ...` 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 ? 1 541463939 ? 2 624015614 ...` 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 ? 1 1 ? 2 2 ...` 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 ? 1 50 ? 2 49 ...` 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 ? 1 1 ? 2 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 ? 1 1 ? 2 2 ...` 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 ? 1 401 ? 2 388 ...` 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 ? 1 34030354 ? 2 571736161 ...` 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 ? 1 1 ? 2 2 ...` 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 ? 1 100 ? 2 99 ...` 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 ? 1 1 ? 2 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 ? 1 2 ? 2 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 ? 1 338 ? 2 877 ...` 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 ? 1 301892461 ? 2 304390263 ...` 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 ? 1 1 ? 2 2 ...` 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 ? 1 1000000 ? 2 999999 ...` 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 ? 1 1000000 ? 2 1000001 ...` 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 ? 1 1000000 ? 2 1000001 ...` 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 ? 1 1000000 ? 2 1000001 ...` 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 (jlaire)