Submission #422033

#	Time	Username	Problem	Language	Result	Execution time	Memory
422033		pure_mem	Scales (IOI15_scales)	C++14	72.02 / 100	219 ms	452 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>

#define ll long long
#define MP make_pair
#define X first
#define Y second

using namespace std;

const int N = 720;

int p[N][6], mans[N][6], bad[N];

struct Event{
    int tp, a, b, c, d;
};
int check(int id, Event x){
    int mn = min(min(p[id][x.a], p[id][x.b]), p[id][x.c]);
    int mx = max(max(p[id][x.a], p[id][x.b]), p[id][x.c]);
    int md = p[id][x.a] + p[id][x.b] + p[id][x.c] - mn - mx;
    int cur;
    if(x.tp == 0) cur = mn;
    else if(x.tp == 1) cur = md;
    else if(x.tp == 2) cur = mx;
    else{
        cur = mn;
        if(mn > p[id][x.d]) cur = mn;
        else if(md > p[id][x.d]) cur = md;
        else if(mx > p[id][x.d]) cur = mx;
    }
    return cur;
}
int calc(Event cur){
    if(cur.tp == -1) return N + 12;
    unordered_map<int, int> mp;
    int mx = 0;
    for(int i = 0, val;i < N;i++){
        if(bad[i]) continue;
        val = check(i, cur);
        if(p[i][cur.a] == val) val = cur.a;
        else if(p[i][cur.b] == val) val = cur.b;
        else val = cur.c;
        mp[val]++;
        mx = max(mx, mp[val]);
    }
    return mx;
}

void prep(Event cur){
    int resp;
    if(cur.tp == 0) resp = getLightest(cur.a + 1, cur.b + 1, cur.c + 1);
    if(cur.tp == 1) resp = getMedian(cur.a + 1, cur.b + 1, cur.c + 1);
    if(cur.tp == 2) resp = getHeaviest(cur.a + 1, cur.b + 1, cur.c + 1);
    if(cur.tp == 3) resp = getNextLightest(cur.a + 1, cur.b + 1, cur.c + 1, cur.d + 1);
    //cerr << cur.tp << " " << cur.a << " " << cur.b << " " << cur.c << " " << cur.d << " " << resp - 1 << "\n";
    int me = 0;
    for(int i = 0;i < N;i++){
        if(bad[i]) continue;
        bad[i] |= (p[i][resp - 1] != check(i, cur));
        me += !bad[i];
    }
}

void init(int T) {
    for(int i = 0;i < 6;i++) p[0][i] = i + 1;
    for(int it = 1;it < N;it++){
        for(int i = 0;i < 6;i++) 
            p[it][i] = p[it - 1][i];
        next_permutation(p[it], p[it] + 6);
    }
    for(int it = 0;it < N;it++){
        for(int i = 0;i < 6;i++)
            mans[it][p[it][i] - 1] = i + 1;
    }
}

int isGood(){
    int x = -1;
    for(int i = 0;i < N;i++){
        if(!bad[i]){ 
            if(x != -1) return -1;
            else x = i;
        }
    }
    return x;
}
    
void orderCoins() {
    for(int i = 0;i < N;i++) bad[i] = 0;

    while(isGood() == -1){

        Event cur = {-1, -1, -1, -1};
        for(int a = 0;a < 6;a++){
            for(int b = a + 1;b < 6;b++){
                for(int c = b + 1;c < 6;c++){
                    Event tmp;
                    tmp = {0, a, b, c, -1};
                    if(calc(cur) > calc(tmp)) cur = tmp;
                    tmp = {1, a, b, c, -1};
                    if(calc(cur) > calc(tmp)) cur = tmp;
                    tmp = {2, a, b, c, -1};
                    if(calc(cur) > calc(tmp)) cur = tmp;
                    for(int d = 0;d < 6;d++){
                        if(a == d || b == d || c == d) continue;
                        tmp = {3, a, b, c, d};
                        if(calc(cur) > calc(tmp)) cur = tmp;
                    }
                }
            }
        }
        prep(cur);

    }
    
    return answer(mans[isGood()]);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:65:15: warning: unused parameter 'T' [-Wunused-parameter]
   65 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:94:36: warning: missing initializer for member 'Event::d' [-Wmissing-field-initializers]
   94 |         Event cur = {-1, -1, -1, -1};
      |                                    ^
scales.cpp: In function 'void prep(Event)':
scales.cpp:51:9: warning: 'resp' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |     int resp;
      |         ^~~~

• Subtask 1: 72.02381 / 100