oj.uz

답안 #590484

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
590484 2022-07-06T03:03:09 Z balbit Super Dango Maker (JOI22_dango3) C++17
100 / 100
 1203 ms 824 KB 
#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

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

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 380 KB Output is correct
2 Correct 13 ms 388 KB Output is correct
3 Correct 13 ms 340 KB Output is correct
4 Correct 14 ms 396 KB Output is correct
5 Correct 12 ms 376 KB Output is correct
6 Correct 13 ms 384 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 279 ms 628 KB Output is correct
2 Correct 288 ms 492 KB Output is correct
3 Correct 305 ms 640 KB Output is correct
4 Correct 308 ms 544 KB Output is correct
5 Correct 275 ms 544 KB Output is correct
6 Correct 266 ms 548 KB Output is correct

Subtask #4
78.0 / 78.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1150 ms 716 KB Output is correct
2 Correct 1101 ms 728 KB Output is correct
3 Correct 1203 ms 736 KB Output is correct
4 Correct 1177 ms 788 KB Output is correct
5 Correct 1041 ms 824 KB Output is correct
6 Correct 1028 ms 732 KB Output is correct