oj.uz

Submission #605003

# Submission time Handle Problem Language Result Execution time Memory
605003 2022-07-25T12:07:52 Z balbit Scales (IOI15_scales) C++14
100 / 100
 8 ms 536 KB 
#include "scales.h"
#include <bits/stdc++.h>
using namespace std;

#define Per array<int, 6>
// #define int ll

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

#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)

#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

#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




struct Move{
    int type, a,b,c,d; // 0-indexed
    int getthat() {
        int R;
        if (type == 0) {
            R = getHeaviest(a+1,b+1,c+1);
        }else if (type == 1) {
            R = getLightest(a+1,b+1,c+1);
        }else if (type == 2) {
            R = getMedian(a+1,b+1,c+1);
        }else{
            R = getNextLightest(a+1,b+1,c+1,d+1);
        }
        if(R == a+1) return 0;
        if(R == b+1) return 1;
        return 2;
    }
    int eval(Per &p) {
        if(type == 0) {
            // heaviest
            if (p[a] > p[b] && p[a] > p[c]) return 0;
            if (p[b] > p[a] && p[b] > p[c]) return 1;
            return 2;
        }
        else if (type == 1) {
            // lightest
            if (p[a] < p[b] && p[a] < p[c]) return 0;
            if (p[b] < p[a] && p[b] < p[c]) return 1;
            return 2;
        }else if (type == 2) {
            // median
            int mx = max({p[a],p[b],p[c]});
            int mn = min({p[a],p[b],p[c]});
            if(p[a] != mx && p[a] != mn) return 0;
            if(p[b] != mx && p[b] != mn) return 1;
            return 2;
        }else{
            // next greater
            vector<pii> P = {make_pair(p[a],0), make_pair(p[b],1), make_pair(p[c],2)};
            sort(ALL(P));
            if(p[d] < P[0].f || p[d] > P[2].f) return P[0].s;
            else if (p[d] < P[1].f) return P[1].s;
            return P[2].s;
        }
    }
};

vector<Move> allmoves;

void build(){
    REP(c,6) REP(b,c) REP(a,b) {
        allmoves.pb({0,a,b,c,-1});
        allmoves.pb({1,a,b,c,-1});
        allmoves.pb({2,a,b,c,-1});
    }

    REP(d,6){
        REP(c,6) REP(b,c) REP(a,b) {
            if (a != d && b != d && c != d) {
                allmoves.pb({3,a,b,c,d});
            }
        }
    }

    bug(SZ(allmoves));
}

vector<Per> allp;
ll P3[10];

Move strat[7][729];
Per ans[7][729];

bool run(vector<Per> go, int targ, int str) {
    // goal:finish in targ moves
    if (SZ(go) == 1) {
        bug(targ, str, go[0][0]);
        ans[targ][str] = go[0];
        return 1;
    }
    if (SZ(go) == 0) {
        return 1;
    }
    if(targ == 0) {
        return 0;
    }
    
    for(Move &m : allmoves) {
        array<vector<Per>, 3> ha;
        bool bad = 0;
        for(Per &p : go) {
            int gt = m.eval(p);
            ha[gt].pb(p);
            if (SZ(ha[gt]) > P3[targ-1]) {
                bad = 1; break;
            }
        }
        if(!bad) {
            if(0) {
                strat[targ][str]=m;
                return 1;
            }else{
                bool okay = 1;
                REP(k,3) {
                    okay &= run(ha[k], targ-1, str * 3 + k);
                    if(okay == 0)break;
                }
                if (okay) {
                    strat[targ][str] = m;
                    // bug(targ, str, m.type);
                    return 1;
                }
                assert(targ != 1);
            }
        }
    }
    return 0;

}

void buildstrat(){
    REP(i,7) REP(j,729) ans[i][j][0] = -1;
    build();

    P3[0] = 1;
    for (int i = 1; i<10; ++i) P3[i] = P3[i-1] *3;
    Per now;
    REP(i,6)now[i]=i;
    do{
        allp.pb(now);
    }while (next_permutation(ALL(now)));
    bug(SZ(allp));
    random_shuffle(ALL(allmoves));

    bool yup = run(allp, 6, 0);
    bug(yup);

}

void orderCoins() {
    /* ... */
    // assert(0);
    
    int str = 0;
    int targ = 6;

    Per yay;
    yay[0] = -1;
    REP(ha, 6) {
        bug(targ, str);
        auto M = strat[targ][str];
        bug(M.type, M.a, M.b, M.c, M.d);
        if (ans[targ][str][0] != -1) {
            bug(targ, str);
            yay = ans[targ][str]; break;
        }
        int yar = strat[targ][str].getthat();
        bug(yar);
        str = str *3 + yar;
        --targ;
    }
    bug(targ, str, ans[targ][str][0]);
    if(yay[0] == -1) yay = ans[targ][str];
    assert(yay[0] != -1);
    vector<pii> re;
    REP(i,6) re.pb({yay[i], i});
    sort(ALL(re));
    int ANS[6];
    REP(i,6) ANS[i]= re[i].s+1/*, bug(i, ANS[i])*/;
    answer(ANS);
}
void init(int T) {
    buildstrat();

}
// signed main(){
//     buildstrat();
// }

Compilation message

scales.cpp: In function 'void buildstrat()':
scales.cpp:169:10: warning: unused variable 'yup' [-Wunused-variable]
  169 |     bool yup = run(allp, 6, 0);
      |          ^~~
scales.cpp: In function 'void orderCoins()':
scales.cpp:185:14: warning: variable 'M' set but not used [-Wunused-but-set-variable]
  185 |         auto M = strat[targ][str];
      |              ^
scales.cpp: In function 'void init(int)':
scales.cpp:206:15: warning: unused parameter 'T' [-Wunused-parameter]
  206 | void init(int T) {
      |           ~~~~^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Output is correct
2 Correct 8 ms 468 KB Output is correct
3 Correct 6 ms 468 KB Output is correct
4 Correct 6 ms 432 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 6 ms 436 KB Output is correct
7 Correct 6 ms 468 KB Output is correct
8 Correct 6 ms 468 KB Output is correct
9 Correct 6 ms 488 KB Output is correct
10 Correct 6 ms 436 KB Output is correct
11 Correct 6 ms 468 KB Output is correct
12 Correct 6 ms 532 KB Output is correct
13 Correct 6 ms 468 KB Output is correct
14 Correct 7 ms 532 KB Output is correct
15 Correct 7 ms 536 KB Output is correct
16 Correct 7 ms 536 KB Output is correct
17 Correct 7 ms 436 KB Output is correct
18 Correct 6 ms 536 KB Output is correct
19 Correct 6 ms 532 KB Output is correct
20 Correct 6 ms 468 KB Output is correct
21 Correct 6 ms 532 KB Output is correct
22 Correct 6 ms 436 KB Output is correct
23 Correct 7 ms 520 KB Output is correct
24 Correct 6 ms 468 KB Output is correct
25 Correct 6 ms 468 KB Output is correct
26 Correct 7 ms 468 KB Output is correct
27 Correct 7 ms 468 KB Output is correct
28 Correct 6 ms 468 KB Output is correct
29 Correct 7 ms 468 KB Output is correct
30 Correct 8 ms 536 KB Output is correct
31 Correct 7 ms 536 KB Output is correct
32 Correct 6 ms 468 KB Output is correct
33 Correct 8 ms 468 KB Output is correct
34 Correct 6 ms 468 KB Output is correct
35 Correct 6 ms 432 KB Output is correct
36 Correct 6 ms 468 KB Output is correct
37 Correct 6 ms 468 KB Output is correct
38 Correct 6 ms 432 KB Output is correct
39 Correct 6 ms 468 KB Output is correct
40 Correct 6 ms 468 KB Output is correct