Submission #346932

#	Time	Username	Problem	Language	Result	Execution time	Memory
346932		jamezzz	Carnival (CEOI14_carnival)	C++14	100 / 100	21 ms	364 KiB

carnival

#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 (stderr)

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20