oj.uz

답안 #619922

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
619922 2022-08-02T17:15:18 Z yanndev 저울 (IOI15_scales) C++17
33.4524 / 100
 1 ms 256 KB 
#include "scales.h"
#include <bits/stdc++.h>
using namespace std;

mt19937 rng(4589);
int mx = -1;
map<pair<int, int>, bool> comp {};

void init(int T) {
    /* ... */
}

bool comp1(int a, int b) {
    if (a == b)
        return false;
    if (comp.find({a, b}) != comp.end())
        return comp[{a, b}];
        
    /*int c = a;
    while (c == a || c == b)
        c = (rng() % 6) + 1;*/
    int c = -1;
    for (int i = 1; i <= 6; i++)
        if (i != a && i != b)
            c = i;

    vector<int> ls {a, b, c};
    
    int small = getLightest(a, b, c);
    for (auto& x: ls) {
        if (x != small) {
            comp[{small, x}] = true;
            comp[{x, small}] = false;
        }
    }

    if (a == small)
        return true;
    if (b == small)
        return false;

    int big = getHeaviest(a, b, c);
    for (auto& x: ls) {
        if (x != big) {
            comp[{x, big}] = true;
            comp[{big, x}] = false;
        }
    }

    if (a == big)
        return false;
    if (b == big)
        return true;
}

bool comp2(int a, int b) {
    if (a == b)
        return false;
    if (comp.find({a, b}) != comp.end())
        return comp[{a, b}];

    int small = getLightest(a, b, mx);
    comp[{a, b}] = small == a;
    comp[{b, a}] = small != a;
    return small == a;
}

void orderCoins() {
    /* ... */
    int W[] = {1, 2, 3, 4, 5, 6};
    shuffle(W, W + 6, rng);
    comp.clear();

    vector<int> cur {};

    for (int i = 0; i < 6; i++) {
        if ((int)cur.size() < 3) {
            cur.push_back(W[i]);
        }

        if ((int)cur.size() == 3) {
            mx = getHeaviest(cur[0], cur[1], cur[2]);
            for (int j = 0; j <= i; j++) {
                if (W[j] != mx) {
                    comp[{mx, W[j]}] = false;
                    comp[{W[j], mx}] = true;
                }
            }
            cur = {mx};
        }
    }

    if ((int)cur.size() > 1) {
        for (int i = 0; (int)cur.size() < 3 && i < 6; i++) {
            if (find(cur.begin(), cur.end(), W[i]) == cur.end()) {
                cur.push_back(W[i]);
            }
        }
        
        mx = getHeaviest(cur[0], cur[1], cur[2]);
    }

    for (int i = 1; i <= 6; i++) {
        if (i != mx) {
            comp[{i, mx}] = true;
            comp[{mx, i}] = false;
        }
    }

    //cout << "mx is " << mx << '\n';

    stable_sort(W, W + 6, comp2);
    answer(W);
}

Compilation message

scales.cpp: In function 'void init(int)':
scales.cpp:9:15: warning: unused parameter 'T' [-Wunused-parameter]
    9 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'bool comp1(int, int)':
scales.cpp:27:28: warning: control reaches end of non-void function [-Wreturn-type]
   27 |     vector<int> ls {a, b, c};
      |                            ^

Subtask #1
33.452381 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Partially correct 1 ms 212 KB Output is partially correct
3 Partially correct 1 ms 212 KB Output is partially correct
4 Partially correct 1 ms 212 KB Output is partially correct
5 Partially correct 1 ms 212 KB Output is partially correct
6 Partially correct 1 ms 212 KB Output is partially correct
7 Partially correct 1 ms 212 KB Output is partially correct
8 Partially correct 1 ms 212 KB Output is partially correct
9 Partially correct 0 ms 212 KB Output is partially correct
10 Partially correct 1 ms 212 KB Output is partially correct
11 Partially correct 1 ms 212 KB Output is partially correct
12 Partially correct 1 ms 212 KB Output is partially correct
13 Partially correct 1 ms 212 KB Output is partially correct
14 Partially correct 1 ms 212 KB Output is partially correct
15 Partially correct 0 ms 212 KB Output is partially correct
16 Partially correct 1 ms 212 KB Output is partially correct
17 Partially correct 1 ms 212 KB Output is partially correct
18 Partially correct 1 ms 212 KB Output is partially correct
19 Partially correct 1 ms 256 KB Output is partially correct
20 Partially correct 1 ms 212 KB Output is partially correct
21 Partially correct 1 ms 212 KB Output is partially correct
22 Partially correct 1 ms 212 KB Output is partially correct
23 Partially correct 1 ms 212 KB Output is partially correct
24 Partially correct 1 ms 212 KB Output is partially correct
25 Partially correct 1 ms 212 KB Output is partially correct
26 Partially correct 1 ms 212 KB Output is partially correct
27 Partially correct 1 ms 212 KB Output is partially correct
28 Partially correct 1 ms 212 KB Output is partially correct
29 Partially correct 1 ms 212 KB Output is partially correct
30 Partially correct 1 ms 212 KB Output is partially correct
31 Partially correct 1 ms 212 KB Output is partially correct
32 Partially correct 1 ms 212 KB Output is partially correct
33 Partially correct 1 ms 212 KB Output is partially correct
34 Partially correct 1 ms 212 KB Output is partially correct
35 Partially correct 1 ms 212 KB Output is partially correct
36 Partially correct 1 ms 212 KB Output is partially correct
37 Partially correct 1 ms 212 KB Output is partially correct
38 Partially correct 1 ms 212 KB Output is partially correct
39 Partially correct 1 ms 212 KB Output is partially correct
40 Partially correct 1 ms 212 KB Output is partially correct