CSES - Putka Open 2025 – 3/5

Submission details
Task:	Kyselyt
Sender:	Kuha
Submission time:	2025-10-18 12:39:16 +0300
Language:	C++ (C++20)
Status:	READY
Result:	60

Feedback
group	verdict	score
#1	ACCEPTED	10
#2	ACCEPTED	20
#3	ACCEPTED	30
#4	WRONG ANSWER	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.01 s	1, 2, 3, 4	details
#2	ACCEPTED	0.01 s	1, 2, 3, 4	details
#3	ACCEPTED	0.01 s	1, 3, 4	details
#4	ACCEPTED	0.20 s	2, 3, 4	details
#5	ACCEPTED	0.22 s	2, 3, 4	details
#6	ACCEPTED	0.41 s	2, 3, 4	details
#7	ACCEPTED	0.57 s	3, 4	details
#8	ACCEPTED	0.40 s	4	details
#9	WRONG ANSWER	0.44 s	4	details
#10	TIME LIMIT EXCEEDED	--	4	details
#11	ACCEPTED	0.43 s	3, 4	details
#12	ACCEPTED	0.85 s	4	details
#13	ACCEPTED	0.22 s	3, 4	details
#14	ACCEPTED	0.45 s	4	details
#15	ACCEPTED	0.43 s	4	details
#16	ACCEPTED	0.41 s	4	details

Code

#include <bits/stdc++.h>

#define N (1<<18)

using namespace std;

int v[N];
int comp[N];
vector<int> mp[N];
map<int, int> enc;
map<int, int> de;

int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    srand(time(0));
    int n, q;
    cin>>n>>q;
    vector<int> vals;
    for (int i = 1; i <= n; i++) {
        cin>>v[i];
        vals.push_back(v[i]);
    }
    vals.push_back(-1);
    sort(vals.begin(), vals.end());
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (vals[i] != vals[i - 1]) cnt++;
        enc[vals[i]] = cnt;
        de[cnt] = vals[i];
    }
    for (int i = 1; i <= n; i++) {
        comp[i] = enc[v[i]];
        mp[comp[i]].push_back(i);
    }
    
    for (int i = 1; i <= n; i++) {
        if (mp[comp[i]].back() != n + 1) mp[comp[i]].push_back(n + 1);
    }
    while (q --> 0) {
        int l, r;
        cin>>l>>r;
        for (int t = 0; t < 20; t++) {
            int len = r - l + 1;
            int i = l + (rand() % len);
            int li = -1;
            int ri = -1;
            int wl = mp[comp[i]].size();
            for (int inc = 1<<17; inc >= 1; inc /= 2) {
                if (li + inc < wl && mp[comp[i]][li + inc] < l) li += inc;
                if (ri + inc < wl && mp[comp[i]][ri + inc] <= r) ri += inc;
            }
            if (2 * (ri - li) > len) {
                cout<<de[comp[i]]<<endl;
                goto end;
            }
        }
        cout<<-1<<endl;
        end:;
    }
}

Test details

Test 1

Group: 1, 2, 3, 4

Verdict: ACCEPTED

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

correct output
`1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 ...` Truncated

Test 2

Group: 1, 2, 3, 4

Verdict: ACCEPTED

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

correct output
`2 1 1 2 1 ...` view save

user output
`2 1 1 2 1 ...` Truncated

Test 3

Group: 1, 3, 4

Verdict: ACCEPTED

input
`100 100 5 19 44 88 14 79 50 44 14 99 7...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` Truncated

Test 4

Group: 2, 3, 4

Verdict: ACCEPTED

input
`100000 100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
`1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 ...` Truncated

Test 5

Group: 2, 3, 4

Verdict: ACCEPTED

input
`100000 100000 1 1 1 2 1 2 1 1 2 1 1 1 1 2 2 ...` view save

correct output
`1 1 2 1 1 ...` view save

user output
`1 1 2 1 1 ...` Truncated

Test 6

Group: 2, 3, 4

Verdict: ACCEPTED

input
`100000 100000 8 2 6 1 10 4 9 7 8 10 4 2 8 2 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` Truncated

Test 7

Group: 3, 4

Verdict: ACCEPTED

input
`100000 100000 141307 493258596 365539511 222...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` Truncated

Test 8

Group: 4

Verdict: ACCEPTED

input
`200000 200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
`1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 ...` Truncated

Test 9

Group: 4

Verdict: WRONG ANSWER

input
`200000 200000 1 2 2 2 1 2 2 1 1 1 1 1 1 1 1 ...` view save

correct output
`2 2 2 2 2 ...` view save

user output
`2 2 2 2 2 ...` Truncated

Test 10

Group: 4

Verdict: TIME LIMIT EXCEEDED

input
`200000 200000 286470749 280175209 741317063 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
(empty)

Test 11

Group: 3, 4

Verdict: ACCEPTED

input
`100000 100000 613084013 1000000000 411999902...` view save

correct output
`-1 -1 -1 -1 1000000000 ...` view save

user output
`-1 -1 -1 -1 1000000000 ...` Truncated

Test 12

Group: 4

Verdict: ACCEPTED

input
`200000 200000 613084013 1000000000 411999902...` view save

correct output
`1000000000 1000000000 -1 1000000000 -1 ...` view save

user output
`1000000000 1000000000 -1 1000000000 -1 ...` Truncated

Test 13

Group: 3, 4

Verdict: ACCEPTED

input
`100000 100000 663307073 663307073 663307073 ...` view save

correct output
`329574367 965067805 768744535 691214891 21873594 ...` view save

user output
`329574367 965067805 768744535 691214891 21873594 ...` Truncated

Test 14

Group: 4

Verdict: ACCEPTED

input
`200000 200000 663307073 663307073 663307073 ...` view save

correct output
`107596959 249558965 679275202 760593154 725418770 ...` view save

user output
`107596959 249558965 679275202 760593154 725418770 ...` Truncated

Test 15

Group: 4

Verdict: ACCEPTED

input
`200000 200000 663307073 663307073 663307073 ...` view save

correct output
`211070558 49212342 651109313 264549124 651109313 ...` view save

user output
`211070558 49212342 651109313 264549124 651109313 ...` Truncated

Test 16

Group: 4

Verdict: ACCEPTED

input
`200000 200000 2 2 2 1 2 1 1 2 2 1 1 1 1 2 1 ...` view save

correct output
`1 2 1 1 1 ...` view save

user output
`1 2 1 1 1 ...` Truncated

Putka Open 2025 – 3/5

Kyselyt

Code

Test details

Test 1

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

Tasks

Submissions (Kuha)