CSES - Putka Open 2025 – 4/5

Submission details
Task:	Huippualkio
Sender:	Metabolix
Submission time:	2025-11-07 18:55:36 +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.01 s	1, 2, 3	details
#2	ACCEPTED	0.01 s	1, 2, 3	details
#3	ACCEPTED	0.01 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.01 s	1, 2, 3	details
#7	ACCEPTED	0.02 s	1, 2, 3	details
#8	ACCEPTED	0.01 s	1, 2, 3	details
#9	ACCEPTED	0.02 s	2, 3	details
#10	ACCEPTED	0.01 s	2, 3	details
#11	ACCEPTED	0.02 s	2, 3	details
#12	ACCEPTED	0.02 s	2, 3	details
#13	ACCEPTED	0.01 s	2, 3	details
#14	ACCEPTED	0.01 s	2, 3	details
#15	ACCEPTED	0.18 s	3	details
#16	ACCEPTED	0.18 s	3	details
#17	ACCEPTED	0.26 s	3	details
#18	ACCEPTED	0.47 s	3	details
#19	ACCEPTED	0.36 s	3	details
#20	ACCEPTED	0.36 s	3	details
#21	ACCEPTED	0.02 s	1, 2, 3	details
#22	ACCEPTED	0.01 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.01 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.01 s	1, 2, 3	details
#31	ACCEPTED	0.01 s	1, 2, 3	details

Code

#include <bits/stdc++.h>

using namespace std;

int n;
map<int, int> muisti;

int kysy(int i) {
    if (i < 1 || i > n) {
        return 0;
    }
    if (muisti.find(i) != muisti.end()) {
        return muisti[i];
    }
    cout << "? " << i << endl;
    int vastaus;
    cin >> vastaus;
    muisti[i] = vastaus;
    return vastaus;
}

void vastaa(int i) {
    cout << "! " << i << endl;
}

int main() {
    cin >> n;
    muisti[0] = 0;
    muisti[n+1] = 0;
    kysy((n + 1) / 2);
    auto huippu = next(muisti.begin());

    while (1) {
        auto vasen = prev(huippu);
        auto oikea = next(huippu);
        int vasen_matka = huippu->first - vasen->first;
        int oikea_matka = oikea->first - huippu->first;
        if (vasen_matka == 1 && oikea_matka == 1) {
            vastaa(huippu->first);
            return 0;
        }
        if (vasen_matka >= oikea_matka) {
            if (kysy(vasen->first + vasen_matka / 2) > huippu->second) {
                huippu = prev(huippu);
            }
        } else {
            if (kysy(huippu->first + oikea_matka / 2) > huippu->second) {
                huippu = next(huippu);
            }
        }
    }
}

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 ? 6 3 ...` 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 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 ? 38 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 ? 38 2 ...` 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 ? 38 88 ...` 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 ? 38 159647580 ...` 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 ? 38 38 ...` 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 ? 38 13 ...` 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 ? 75 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 ? 75 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 ? 50 786 ? 75 587 ...` 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 ? 75 897789362 ...` 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 ? 75 75 ...` 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 ? 75 26 ...` 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 ? 750000 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 ? 750000 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 ? 750000 370 ...` 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 ? 750000 624292991 ...` 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 ? 750000 750000 ...` 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 ? 750000 250001 ...` 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 ? 38 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 ? 75 999984 ...` 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 ? 750000 997825 ...` 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 1000000000 ! 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 ? 2 1 ? 1 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 ? 2 1 ? 1 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 ? 2 2 ? 1 1 ...` 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 ? 2 1 ? 1 2 ...` 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 (Metabolix)