제출 #1148774

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148774		dosts	사육제 (CEOI14_carnival)	C++20	0 / 100	3 ms	440 KiB

carnival

#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 1e18,N = 3e5+1,MOD = 998244353,B = 250;


struct FT {
    vi bit;
    int n;

    FT(int nn) {
        n = nn;
        bit.assign(n+1,0);
    }
    void put(int p,int v) {
        for (int i = p;i<=n;i+=i&-i) bit[i]+=v;
    }

    int get(int p) {
        int ans = 0;
        for (int i = p;i>0;i-=i&-i) ans+=bit[i];
        return ans;
    }
    int get(int l,int r) {
        return get(r)-get(l-1);
    }
};

int ask(int l,int r) {
    assert(l <= r);
    cout << r-l+1 << ' ';
    for (int j = l;j<=r;j++) cout << j << ' ';
    cout << endl;
    int x;
    cin >> x;
    return x;
}

void solve() { 
    int n;
    cin >> n;
    FT ft(n);
    int party = 0;
    vi prv(n+1,-1);
    for (int i=1;i<=n;i++) {
        int dist = ask(1,i);
        if (dist != party) {
            party++;
            ft.put(i,1);
            continue;
        }   
        int l = 1;
        int r = i-1;
        while (l<=r) {
            int m = (l+r) >> 1;
            int d2 = ask(m,i);
            if (d2 == ft.get(m,i-1)+1) r = m-1;
            else l = m+1;
        }
        prv[i] = l-1;
        ft.put(i,1);
        ft.put(prv[i],-1);
    }
    vi col(n+1);
    int ctr = 0;
    cout << 0 << ' ';
    for (int i=1;i<=n;i++) {
        if (prv[i] == -1) {
            col[i] = ++ctr;
            cout << col[i] << ' ';
        }
        else cout << col[prv[i]] << ' ';
    }
    cout << endl;
}

int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
/*     #ifdef Dodi 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif */
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20