oj.uz

Submission #422034

# Submission time Handle Problem Language Result Execution time Memory
422034 2021-06-09T15:27:32 Z pure_mem Scales (IOI15_scales) C++14
72.9167 / 100
 229 ms 324 KB 
#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

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.916667 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 201 ms 204 KB Output is partially correct
2 Partially correct 206 ms 204 KB Output is partially correct
3 Partially correct 206 ms 304 KB Output is partially correct
4 Partially correct 207 ms 304 KB Output is partially correct
5 Partially correct 220 ms 204 KB Output is partially correct
6 Partially correct 209 ms 324 KB Output is partially correct
7 Correct 209 ms 300 KB Output is correct
8 Correct 205 ms 312 KB Output is correct
9 Partially correct 208 ms 204 KB Output is partially correct
10 Partially correct 204 ms 308 KB Output is partially correct
11 Partially correct 202 ms 304 KB Output is partially correct
12 Partially correct 203 ms 308 KB Output is partially correct
13 Partially correct 204 ms 308 KB Output is partially correct
14 Partially correct 200 ms 204 KB Output is partially correct
15 Correct 201 ms 204 KB Output is correct
16 Correct 205 ms 316 KB Output is correct
17 Partially correct 200 ms 204 KB Output is partially correct
18 Partially correct 203 ms 312 KB Output is partially correct
19 Partially correct 217 ms 300 KB Output is partially correct
20 Partially correct 203 ms 304 KB Output is partially correct
21 Partially correct 212 ms 204 KB Output is partially correct
22 Partially correct 202 ms 204 KB Output is partially correct
23 Partially correct 206 ms 204 KB Output is partially correct
24 Partially correct 205 ms 204 KB Output is partially correct
25 Partially correct 229 ms 300 KB Output is partially correct
26 Partially correct 205 ms 316 KB Output is partially correct
27 Partially correct 205 ms 300 KB Output is partially correct
28 Partially correct 204 ms 204 KB Output is partially correct
29 Partially correct 203 ms 312 KB Output is partially correct
30 Partially correct 210 ms 304 KB Output is partially correct
31 Partially correct 208 ms 300 KB Output is partially correct
32 Partially correct 206 ms 304 KB Output is partially correct
33 Partially correct 203 ms 204 KB Output is partially correct
34 Correct 207 ms 304 KB Output is correct
35 Partially correct 200 ms 304 KB Output is partially correct
36 Partially correct 209 ms 304 KB Output is partially correct
37 Partially correct 213 ms 324 KB Output is partially correct
38 Partially correct 204 ms 204 KB Output is partially correct
39 Partially correct 206 ms 300 KB Output is partially correct
40 Partially correct 200 ms 204 KB Output is partially correct