# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
433465 | Tangent | 저울 (IOI15_scales) | C++17 | 4 ms | 308 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "scales.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
#define ffor(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define fford(i, a, b) for (ll i = (a); i > (ll)(b); i--)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()
inline int gm(int A, int B, int C) {
if (B < A && A < C)
return 0;
if (C < A && A < B)
return 0;
if (A < B && B < C)
return 1;
if (C < B && B < A)
return 1;
return 2;
}
inline int gh(int A, int B, int C) {
if (A > B && A > C)
return 0;
if (B > A && B > C)
return 1;
return 2;
}
inline int gl(int A, int B, int C) {
if (A < B && A < C)
return 0;
if (B < A && B < C)
return 1;
return 2;
}
inline int gnl(int A, int B, int C, int D) {
int allLess = 1;
if (A > D || B > D || C > D)
allLess = 0;
if (allLess == 1) {
if (A < B && A < C)
return 0;
if (B < A && B < C)
return 1;
return 2;
}
if (A > D) {
if ((A < B || B < D) && (A < C || C < D))
return 0;
}
if (B > D) {
if ((B < A || A < D) && (B < C || C < D))
return 1;
}
return 2;
}
const vvii combis = {{0, 1, 2}, {0, 1, 3}, {0, 1, 4}, {0, 1, 5}, {0, 2, 3}, {0, 2, 4}, {0, 2, 5}, {0, 3, 4}, {0, 3, 5}, {0, 4, 5}, {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}};
void init(int T) {
}
void orderCoins() {
vvii curr;
vii x = {1, 2, 3, 4, 5, 6};
int a = getLightest(1, 2, 3) - 1, b = getHeaviest(4, 5, 6) - 4;
do {
if (gl(x[0], x[1], x[2]) == a && gh(x[3], x[4], x[5]) == b) {
curr.emplace_back(x);
}
} while(next_permutation(all(x)));
while (curr.size() > 1) {
int bmax = curr.size();
int bc = -1, bt = -1;
rep(i, combis.size()) {
auto &combi = combis[i];
vii cnts(3);
forin(p, curr) {
cnts[gl(p[combi[0]], p[combi[1]], p[combi[2]])]++;
}
int cmax = max(cnts[0], max(cnts[1], cnts[2]));
if (cmax < bmax) {
bmax = cmax;
bc = i;
bt = 0;
}
cnts.assign(3, 0);
forin(p, curr) {
cnts[gm(p[combi[0]], p[combi[1]], p[combi[2]])]++;
}
cmax = max(cnts[0], max(cnts[1], cnts[2]));
if (cmax < bmax) {
bmax = cmax;
bc = i;
bt = 1;
}
cnts.assign(3, 0);
forin(p, curr) {
cnts[gh(p[combi[0]], p[combi[1]], p[combi[2]])]++;
}
cmax = max(cnts[0], max(cnts[1], cnts[2]));
if (cmax < bmax) {
bmax = cmax;
bc = i;
bt = 2;
}
cnts.assign(3, 0);
forin(p, curr) {
cnts[gnl(p[combi[0]], p[combi[1]], p[combi[2]], p[combis[19 - i][0]])]++;
}
cmax = max(cnts[0], max(cnts[1], cnts[2]));
if (cmax < bmax) {
bmax = cmax;
bc = i;
bt = 3;
}
cnts.assign(3, 0);
forin(p, curr) {
cnts[gnl(p[combi[0]], p[combi[1]], p[combi[2]], p[combis[19 - i][1]])]++;
}
cmax = max(cnts[0], max(cnts[1], cnts[2]));
if (cmax < bmax) {
bmax = cmax;
bc = i;
bt = 4;
}
cnts.assign(3, 0);
forin(p, curr) {
cnts[gnl(p[combi[0]], p[combi[1]], p[combi[2]], p[combis[19 - i][2]])]++;
}
cmax = max(cnts[0], max(cnts[1], cnts[2]));
if (cmax < bmax) {
bmax = cmax;
bc = i;
bt = 5;
}
}
vvii ncurr;
auto combi = combis[bc];
if (bt == 0) {
int ans = getLightest(combi[0] + 1, combi[1] + 1, combi[2] + 1);
if (ans == combi[0] + 1) {
ans = 0;
} else if (ans == combi[1] + 1) {
ans = 1;
} else {
ans = 2;
}
forin(p, curr) {
if (gl(p[combi[0]], p[combi[1]], p[combi[2]]) == ans) {
ncurr.emplace_back(p);
}
}
} else if (bt == 1) {
int ans = getMedian(combi[0] + 1, combi[1] + 1, combi[2] + 1);
if (ans == combi[0] + 1) {
ans = 0;
} else if (ans == combi[1] + 1) {
ans = 1;
} else {
ans = 2;
}
forin(p, curr) {
if (gm(p[combi[0]], p[combi[1]], p[combi[2]]) == ans) {
ncurr.emplace_back(p);
}
}
} else if (bt == 2) {
int ans = getHeaviest(combi[0] + 1, combi[1] + 1, combi[2] + 1);
if (ans == combi[0] + 1) {
ans = 0;
} else if (ans == combi[1] + 1) {
ans = 1;
} else {
ans = 2;
}
forin(p, curr) {
if (gh(p[combi[0]], p[combi[1]], p[combi[2]]) == ans) {
ncurr.emplace_back(p);
}
}
} else {
int d = combis[19 - bc][bt - 3];
int ans = getNextLightest(combi[0] + 1, combi[1] + 1, combi[2] + 1, d + 1);
if (ans == combi[0] + 1) {
ans = 0;
} else if (ans == combi[1] + 1) {
ans = 1;
} else {
ans = 2;
}
forin(p, curr) {
if (gnl(p[combi[0]], p[combi[1]], p[combi[2]], p[d]) == ans) {
ncurr.emplace_back(p);
}
}
}
curr = move(ncurr);
}
int res[] = {0, 0, 0, 0, 0, 0};
rep(i, 6) {
res[curr[0][i] - 1] = i + 1;
}
answer(res);
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |