# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
422033 | pure_mem | 저울 (IOI15_scales) | C++14 | 219 ms | 452 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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()]);
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |