oj.uz

Submission #346932

# Submission time Handle Problem Language Result Execution time Memory
346932 2021-01-11T11:20:40 Z jamezzz Carnival (CEOI14_carnival) C++14
100 / 100
 21 ms 364 KB 
#include <bits/stdc++.h>
using namespace std;

int n, ft[155], col[155];

void up(int x, int v){
    while (x <= n){
        ft[x] += v;
        x += x & -x;
    }
}

int qry(int x){
    int res = 0;
    while (x){
        res += ft[x];
        x -= x & -x;
    }
    return res;
}

int query(int x, int y){
    printf("%d ", y - x + 1);
    for (int i = x; i <= y; ++i){
        printf("%d ", i);
    }
    printf("\n"); fflush(stdout);
    int t; scanf("%d", &t);
    return t;
}

int main(){
    scanf("%d", &n);
    int cur = 1;
    for (int i = 1; i <= n; ++i){
        int t = query(1, i);
        up(i, t); up(i + 1, -t);
        if (qry(i) != qry(i - 1)) col[i] = cur++;
    }
    col[1] = 1; up(1, -1);
    for (int i = 2; i <= n; ++i){
        int lo = i, hi = n, mid, res = n + 1;
        while (lo <= hi){
            mid = (lo + hi) / 2;
            if (query(i, mid) != qry(mid)){
                hi = mid - 1; res = mid;
            }
            else{
                lo = mid + 1;
            }
        }
        col[res] = col[i - 1];
        up(res, 1); up(i, -1);
    }
    printf("0 ");
    for (int i = 1; i <= n; ++i) printf("%d ", col[i]);
    fflush(stdout);
    return 0;
}

//1 2 1 3 2 3

Compilation message

carnival.cpp: In function 'int query(int, int)':
carnival.cpp:28:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |     int t; scanf("%d", &t);
      |            ~~~~~^~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 364 KB Output is correct
2 Correct 13 ms 364 KB Output is correct
3 Correct 13 ms 364 KB Output is correct
4 Correct 17 ms 364 KB Output is correct
5 Correct 10 ms 364 KB Output is correct
6 Correct 11 ms 364 KB Output is correct
7 Correct 8 ms 364 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 364 KB Output is correct
2 Correct 12 ms 364 KB Output is correct
3 Correct 15 ms 364 KB Output is correct
4 Correct 18 ms 364 KB Output is correct
5 Correct 8 ms 364 KB Output is correct
6 Correct 14 ms 364 KB Output is correct
7 Correct 15 ms 364 KB Output is correct

Subtask #4
20.0 / 20.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 364 KB Output is correct
2 Correct 13 ms 364 KB Output is correct
3 Correct 19 ms 364 KB Output is correct
4 Correct 18 ms 364 KB Output is correct
5 Correct 16 ms 364 KB Output is correct
6 Correct 17 ms 364 KB Output is correct
7 Correct 18 ms 364 KB Output is correct