Submission #590484

#	Time	Username	Problem	Language	Result	Execution time	Memory
590484		balbit	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	1203 ms	824 KiB

dango3

#ifndef BALBIT
#include "dango3.h"
#endif // BALBIT

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<ll, ll>
#define f first
#define s second

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
#define pb push_back


#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)

#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do( T && x ){cerr<<x<<endl;}
template<typename T, typename ...S> void _do( T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT

const int maxn = 3e5+5;

namespace {

int variable_example = 1;

#ifdef BALBIT

vector<int> actval;
int N, M;
int Query(vector<int> v) {
    vector<int> tmp(N);
    for (int e : v) {
        tmp[actval[e-1]]++;
    }
    return *min_element(ALL(tmp));
}
void build(){
    REP(i,N) REP(j,M) actval.pb(i);
    random_shuffle(ALL(actval));
    bug("actval");
    REP(i, SZ(actval)) cout<<actval[i]<<' ';
    cout<<endl<<endl;
}
void Answer(vector<int> e) {
    bug("ans");
    for (int x : e) cout<<x<<' ';
    cout<<endl;
}
#endif // BALBIT

void run(int n, int m, vector<int> go) {
    if (m == 1) {
        Answer(go); return;
    }
    int mid = (m/2);
    vector<int> canrem (SZ(go));
    REP(i, SZ(go)) {
        canrem[i] = 1;
        vector<int> tmp;
        REP(j, SZ(go)) {
            if (!canrem[j]) tmp.pb(go[j]);
        }
        if (Query(tmp) >= mid) {
            // good!
        }else{
            canrem[i] = 0;
        }
    }
    vector<int> gl, gr;
    REP(i, SZ(go)) {
        (canrem[i]?gl:gr).pb(go[i]);
    }
    bug(SZ(gl), SZ(gr));
    run(n,mid,gr); run(n,m-mid,gl);
}

}  // namespace

void Solve(int n, int m) {

    mt19937 rng (chrono::steady_clock::now().time_since_epoch().count());

    vector<int> left;

    REP1(i,n*m) left.pb(i);

    run(n,m,left);

}



#ifdef BALBIT
signed main(){
    bug("hi");
    N = 4, M = 3;
    build();
    Solve(N,M);

}
#endif // BALBIT

Compilation message (stderr)

dango3.cpp:38:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
   38 | int variable_example = 1;
      |     ^~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 78 / 78