Submission #1137800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137800		eggx50000	Take-out (POI13_usu)	C++20	88 / 100	433 ms	73376 KiB

usu

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <random>
#include <set>
#include <queue>
#include <assert.h>
using namespace std;
using ll = long long;
const ll mod = 1000000007;

int n, m, k, cnt[1000099], cp[500099];
char ca[1000099];

struct Ufo{
    int par[500099], en[500099];

    void ini(){
        for(int i = 1; i <= m; i ++) en[i] = i;
    }

    int fi(int a){
        if(par[a] == 0) return a;
        else return par[a] = fi(par[a]);
    }

    int nd(int a){
        return en[fi(a)];
    }

    void uni(int a, int b){
        a = fi(a); b = fi(b);
        if(a == b) return;
        if(a > b) swap(a, b);
        par[b] = a;
        en[a] = en[b];
        cnt[a] += cnt[b] - k;
    }

} uff;

set <int> se;
queue <int> que;
vector <vector<int>> ret;

int main()
{
    scanf("%d %d", &n, &k);
    scanf("%s", ca + 1);
    for(int i = 1; i <= n; i ++) se.insert(i);
    int yu = 0;
    m = 1;
    for(int i = 1; i <= n; i ++){
        if(ca[i] == 'c'){
            cp[m] = i;
            m ++;
        }
        else cnt[m] ++;
    }
    uff.ini();
    for(int i = 1; i <= m - 1; i ++){
        if(cnt[i] + cnt[i + 1] >= k) que.push(i);
    }
    while(que.size()){
        int fr = que.front();
        que.pop();
        if(cp[fr] == 0 || cnt[uff.fi(fr)] + cnt[uff.fi(fr + 1)] < k) continue;
        int pp = k;
        vector <int> vv;
        vv.push_back(cp[fr]);
        se.erase(cp[fr]);
        while(pp){
            auto it = se.lower_bound(cp[fr]);
            if(it == se.begin()) break;
            it --;
            if(ca[*it] == 'c') break;
            vv.push_back(*it);
            se.erase(it);
            pp --;
        }
        while(pp){
            auto it = se.upper_bound(cp[fr]);
            if(it == se.end() || ca[*it] == 'c') break;
            vv.push_back(*it);
            se.erase(it);
            pp --;
        }
        sort(vv.begin(), vv.end());
        ret.push_back(vv);
        cp[fr] = 0;
        uff.uni(fr, fr + 1);
        int s = uff.fi(fr), e = uff.nd(fr);
        if(s - 1 && cnt[uff.fi(s - 1)] + cnt[s] >= k) que.push(s - 1);
        if(e + 1 <= m && cnt[s] + cnt[e + 1] >= k) que.push(e);
    }
    for(int i = ret.size() - 1; i >= 0; i --){
        for(int &e : ret[i]) printf("%d ", e);
        printf("\n");
    }
    return 0;
}

Compilation message (stderr)

usu.cpp: In function 'int main()':
usu.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
usu.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%s", ca + 1);
      |     ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 0 / 12