oj.uz

Submission #531823

# Submission time Handle Problem Language Result Execution time Memory
531823 2022-03-01T15:37:17 Z christinelynn Carnival (CEOI14_carnival) C++17
100 / 100
 19 ms 320 KB 
#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>>segments;
int color[152];

int ask(int x, int y){
    cout << (y - x + 1) << " ";
    for(int i = x; i <= y; i++) cout << i << " ";
    cout << endl;
    int ret; cin >> ret;
    return ret;
}

int getSegment(int l, int r){
    vector<bool>mark(152);
    int cnt = 0;
    for(int i = l; i <= r; i++){
        if(!mark[color[i]]){
            mark[color[i]] = true;
            cnt++;
        }
    }

    return cnt;
}

int main(){ 
    int n; cin >> n;
    int L = 1, R = 1;

    for(int i = 1; i <= n; i++){
        int tmp = 0;
        if(i != n) tmp = ask(i, i + 1);

        if(tmp == 1) R = i + 1;
        else{
            segments.emplace_back(L, R);
            L = R = i + 1;
        }
    }

    color[0] = 1;
    color[1] = 2;
    int lc = 2;

    for(int i = 2; i < segments.size(); i++){
        int l = 0, r = i - 1;
        int col = lc + 1;

        while(l <= r){
            int m = (l + r)/2;

            int cursegment = getSegment(m, i - 1) + 1;
            int nahlo = ask(segments[m].first, segments[i].first);
            
            if(cursegment > nahlo){
                l = m + 1;
                col = color[m];
            } else{
                r = m - 1;
            }
        }

        if(col == lc + 1) lc++;

        color[i] = col;
    }   

    cout << "0 ";
    for(int i = 0; i < segments.size(); i++){
        auto &[l, r] = segments[i];
        for(int j = l; j <= r; j++) cout << color[i] << " ";
    }
    cout << endl;

    return 0;
}

Compilation message

carnival.cpp: In function 'int main()':
carnival.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i = 2; i < segments.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~
carnival.cpp:72:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int i = 0; i < segments.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 200 KB Output is correct
2 Correct 15 ms 200 KB Output is correct
3 Correct 12 ms 200 KB Output is correct
4 Correct 14 ms 200 KB Output is correct
5 Correct 6 ms 292 KB Output is correct
6 Correct 2 ms 200 KB Output is correct
7 Correct 11 ms 200 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 200 KB Output is correct
2 Correct 11 ms 200 KB Output is correct
3 Correct 10 ms 200 KB Output is correct
4 Correct 12 ms 200 KB Output is correct
5 Correct 7 ms 200 KB Output is correct
6 Correct 3 ms 200 KB Output is correct
7 Correct 11 ms 200 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 200 KB Output is correct
2 Correct 10 ms 200 KB Output is correct
3 Correct 19 ms 296 KB Output is correct
4 Correct 14 ms 200 KB Output is correct
5 Correct 11 ms 320 KB Output is correct
6 Correct 8 ms 300 KB Output is correct
7 Correct 10 ms 200 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 288 KB Output is correct
2 Correct 9 ms 200 KB Output is correct
3 Correct 15 ms 200 KB Output is correct
4 Correct 18 ms 292 KB Output is correct
5 Correct 9 ms 200 KB Output is correct
6 Correct 6 ms 292 KB Output is correct
7 Correct 15 ms 200 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 200 KB Output is correct
2 Correct 13 ms 200 KB Output is correct
3 Correct 12 ms 200 KB Output is correct
4 Correct 16 ms 200 KB Output is correct
5 Correct 17 ms 200 KB Output is correct
6 Correct 15 ms 292 KB Output is correct
7 Correct 17 ms 200 KB Output is correct