제출 #1148776

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148776		dosts	사육제 (CEOI14_carnival)	C++20	100 / 100	4 ms	2780 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);
    }
};

vi arr(N);
set<int> s;
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;
    #ifndef Dodi 
        cin >> x;
    #else 
        for (int j = l;j<=r;j++) {
            s.insert(arr[j]);
        }
        x = s.size();
        s.clear();
    #endif
    return x;
}

void solve() { 
    int n;
    cin >> n;
    #ifdef Dodi 
        for (int i = 1;i<=n;i++) cin >> arr[i];
    #endif
    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 {
            col[i] = col[prv[i]]; 
            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: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20