# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
562939 | hoanghq2004 | 저울 (IOI15_scales) | C++14 | 95 ms | 468 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "scales.h"
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 gen(std :: chrono :: system_clock :: now().time_since_epoch().count());
//
//int A[6];
//
//int getHeaviest(int a, int b, int c) {
// if (A[a] > A[b] && A[a] > A[c]) return a;
// if (A[b] > A[a] && A[b] > A[c]) return b;
// return c;
//}
//
//int getLightest(int a, int b, int c) {
// if (A[a] < A[b] && A[a] < A[c]) return a;
// if (A[b] < A[a] && A[b] < A[c]) return b;
// return c;
//}
//int getMedian(int a, int b, int c) {
// if (A[a] > A[b] && A[a] < A[c]) return a;
// if (A[a] > A[c] && A[a] < A[b]) return a;
// if (A[b] > A[a] && A[b] < A[c]) return b;
// if (A[b] > A[c] && A[b] < A[a]) return b;
// return c;
//}
//
//int getNextLightest(int a, int b, int c, int d) {
// int x = -1;
// if (A[a] > A[d] && (x == -1 || A[a] < A[x])) x = a;
// if (A[b] > A[d] && (x == -1 || A[b] < A[x])) x = b;
// if (A[c] > A[d] && (x == -1 || A[c] < A[x])) x = c;
// if (x != -1) return x;
// return getLightest(a, b, c);
//}
set <vector <int> > s;
struct query {
int a, b, c, d, type;
int operator < (const query& other) const {
return make_tuple(a, b, c, d, type) < make_tuple(other.a, other.b, other.c, other.d, other.type);
}
};
vector <query> ask;
void init(int T) {
vector <int> p;
for (int i = 0; i < 6; ++i) p.push_back(i);
do {
s.insert(p);
} while (next_permutation(p.begin(), p.end()));
for (int a = 0; a < 6; ++a)
for (int b = a + 1; b < 6; ++b)
for (int c = b + 1; c < 6; ++c) {
ask.push_back({a, b, c, 0, 0});
ask.push_back({a, b, c, 0, 1});
ask.push_back({a, b, c, 0, 2});
for (int d = 0; d < 6; ++d) {
if (a == d || b == d || c == d) continue;
ask.push_back({a, b, c, d, 3});
}
}
}
vector <query> Q;
#define max(a, b, c) max({a, b, c})
#define min(a, b, c) min({a, b, c})
//void answer(int W[]) {
// for (int i = 0; i < 6; ++i) assert(W[i] == A[i + 1]), cout << W[i] << ' ';
// cout << endl;
//}
void orderCoins() {
srand(time(nullptr));
set <vector <int> > cands = s;
while (1) {
random_shuffle(ask.begin(), ask.end());
if (cands.size() == 1) {
int W[6];
for (int i = 0; i < 6; ++i) W[(*cands.begin())[i]] = i + 1;
answer(W);
return;
}
query best;
int cur = 1e9;
for (auto _: ask) {
auto [a, b, c, d, type] = _;
if (type == 0) {
int cnt_a = 0, cnt_b = 0, cnt_c = 0;
for (auto p: cands) {
if (max(p[a], p[b], p[c]) == p[a]) ++cnt_a;
if (max(p[a], p[b], p[c]) == p[b]) ++cnt_b;
if (max(p[a], p[b], p[c]) == p[c]) ++cnt_c;
}
if (cur > max(cnt_a, cnt_b, cnt_c)) {
cur = max(cnt_a, cnt_b, cnt_c);
best = _;
}
} else if (type == 1) {
int cnt_a = 0, cnt_b = 0, cnt_c = 0;
for (auto p: cands) {
if (min(p[a], p[b], p[c]) == p[a]) ++cnt_a;
if (min(p[a], p[b], p[c]) == p[b]) ++cnt_b;
if (min(p[a], p[b], p[c]) == p[c]) ++cnt_c;
}
if (cur > max(cnt_a, cnt_b, cnt_c)) {
cur = max(cnt_a, cnt_b, cnt_c);
best = _;
}
} else if (type == 2) {
int cnt_a = 0, cnt_b = 0, cnt_c = 0;
for (auto p: cands) {
if (min(p[a], p[b], p[c]) != p[a] && max(p[a], p[b], p[c]) != p[a]) ++cnt_a;
if (min(p[a], p[b], p[c]) != p[b] && max(p[a], p[b], p[c]) != p[b]) ++cnt_b;
if (min(p[a], p[b], p[c]) != p[c] && max(p[a], p[b], p[c]) != p[c]) ++cnt_c;
}
if (cur > max(cnt_a, cnt_b, cnt_c)) {
cur = max(cnt_a, cnt_b, cnt_c);
best = _;
}
} else {
int cnt_a = 0, cnt_b = 0, cnt_c = 0;
for (auto p: cands) {
int x = -1;
if (p[a] > p[d] && (x == -1 || p[a] < p[x])) x = a;
if (p[b] > p[d] && (x == -1 || p[b] < p[x])) x = b;
if (p[c] > p[d] && (x == -1 || p[c] < p[x])) x = c;
if (x == -1) {
x = a;
if (p[b] < p[x]) x = b;
if (p[c] < p[x]) x = c;
}
if (x == a) ++cnt_a;
if (x == b) ++cnt_b;
if (x == c) ++cnt_c;
}
if (cur > max(cnt_a, cnt_b, cnt_c)) {
cur = max(cnt_a, cnt_b, cnt_c);
best = _;
}
}
}
auto [a, b, c, d, type] = best;
set <vector <int> > ncands;
if (type == 0) {
int x = getHeaviest(a + 1, b + 1, c + 1) - 1;
for (auto p: cands)
if (max(p[a], p[b], p[c]) == p[x]) ncands.insert(p);
} else if (type == 1) {
int x = getLightest(a + 1, b + 1, c + 1) - 1;
for (auto p: cands)
if (min(p[a], p[b], p[c]) == p[x]) ncands.insert(p);
} else if (type == 2) {
int x = getMedian(a + 1, b + 1, c + 1) - 1;
for (auto p: cands)
if (max(p[a], p[b], p[c]) != p[x] && min(p[a], p[b], p[c]) != p[x]) ncands.insert(p);
} else {
int x = getNextLightest(a + 1, b + 1, c + 1, d + 1) - 1;
for (auto p: cands) {
int y = -1;
if (p[a] > p[d] && (y == -1 || p[a] < p[y])) y = a;
if (p[b] > p[d] && (y == -1 || p[b] < p[y])) y = b;
if (p[c] > p[d] && (y == -1 || p[c] < p[y])) y = c;
if (y == -1) {
y = a;
if (p[b] < p[y]) y = b;
if (p[c] < p[y]) y = c;
}
if (x == y) ncands.insert(p);
}
}
swap(cands, ncands);
}
}
////
//int main() {
// ios :: sync_with_stdio(0); cin.tie(0);
// int T;
// cin >> T;
// init(T);
// for (int i = 1; i <= T; ++i) {
// for (int j = 1; j <= 6; ++j) cin >> A[j];
// orderCoins();
// }
//// orderCoins();
//}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |