CSES - Putka Open 2025 – 3/5

Submission details
Task:	Kyselyt
Sender:	tykkipeli
Submission time:	2025-10-17 20:06:52 +0300
Language:	C++ (C++20)
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	10
#2	ACCEPTED	20
#3	ACCEPTED	30
#4	ACCEPTED	40

Test results
test	verdict	time	group
#1	ACCEPTED	0.00 s	1, 2, 3, 4	details
#2	ACCEPTED	0.01 s	1, 2, 3, 4	details
#3	ACCEPTED	0.00 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.22 s	2, 3, 4	details
#7	ACCEPTED	0.12 s	3, 4	details
#8	ACCEPTED	0.42 s	4	details
#9	ACCEPTED	0.42 s	4	details
#10	ACCEPTED	0.27 s	4	details
#11	ACCEPTED	0.26 s	3, 4	details
#12	ACCEPTED	0.53 s	4	details
#13	ACCEPTED	0.08 s	3, 4	details
#14	ACCEPTED	0.16 s	4	details
#15	ACCEPTED	0.87 s	4	details
#16	ACCEPTED	0.37 s	4	details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~

Code

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


int N = 700;
int x[200002];
map<int,int> m, comM;
int mrev[200002]; 
int comMrev[200002]; 
int cnts[200002];
vector<int> commons, commonsM;
int pref[200002][580];


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

    int n,q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> x[i];
    vector<int> v;
    for (int i = 1; i <= n; i++) v.push_back(x[i]);
    sort(v.begin(), v.end());
    int k = 0;
    for (int i = 0; i < v.size(); i++) {
        if (i == 0 || v[i] != v[i-1]) {
            k++;
            mrev[k] = v[i];
            m[v[i]] = k;
        }
    }
    for (int i = 1; i <= n; i++) x[i] = m[x[i]];
    for (int i = 1; i <= n; i++)  cnts[x[i]]++;
    for (int i = 1; i <= 200000; i++) {
        if (cnts[i] >= N/2) commons.push_back(i);
    }

    k = 0;
    for (int a : commons) {
        k++;
        comM[a] = k;
        comMrev[k] = a;
    }

    for (int b : commons) {
        int a = comM[b];
        commonsM.push_back(a);
        for (int i = 1; i <= n; i++) {
            pref[i][a] = pref[i-1][a];
            if (x[i] == b) pref[i][a]++;
        }
    }

    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        int cmn = 0;
        int cmncnt = 0;
        if (b-a+1 <= N) {
            for (int j = a; j <= b; j++) cnts[x[j]] = 0;
            for (int j = a; j <= b; j++) {
                cnts[x[j]]++;
                if (cnts[x[j]] > cmncnt) {
                    cmncnt = cnts[x[j]];
                    cmn = x[j];
                }
            }
        } else {
            for (int z : commonsM) {
                int cntt = pref[b][z] - pref[a-1][z];
                if (cntt > cmncnt) {
                    cmncnt = cntt;
                    cmn = z;
                }
            }
            cmn = comMrev[cmn];
        }
        if (2*cmncnt > b-a+1) {
            cout << mrev[cmn] << "\n";
        } else {
            cout << -1 << "\n";
        }
    }

}

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: ACCEPTED

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: ACCEPTED

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

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

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

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

Compiler report

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 (tykkipeli)