제출 #429100

#제출 시각아이디문제언어결과실행 시간메모리
429100timmyfeng저울 (IOI15_scales)C++17
0 / 100
671 ms7792 KiB
#include <bits/stdc++.h> using namespace std; #include "scales.h" const int N = 6, M = 720, P[] = {1, 3, 9, 27, 81, 243, 729}; map<vector<int>, array<int, 4>> compare; vector<int> perm[M], inv[M]; int ans[N]; void sort(vector<int> &p, int &i, int &j, int &k) { if (p[i] > p[j]) { swap(i, j); } if (p[j] > p[k]) { swap(j, k); } if (p[i] > p[j]) { swap(i, j); } } int lightest(vector<int> &p, int i, int j, int k) { sort(p, i, j, k); return i; } int heaviest(vector<int> &p, int i, int j, int k) { sort(p, i, j, k); return k; } int median(vector<int> &p, int i, int j, int k) { sort(p, i, j, k); return j; } int next(vector<int> &p, int i, int j, int k, int l) { sort(p, i, j, k); if (p[l] < p[i]) { return i; } else if (p[l] < p[j]) { return j; } else if (p[l] < p[k]) { return k; } else { return i; } } bool solve(vector<int> mask, int remain) { if (mask.size() <= 1) { return true; } else if ((int) mask.size() > P[remain]) { return false; } else if (compare.count(mask) > 0) { return true; } vector<int> one, two, three; for (int i = 0; i < N; ++i) { for (int j = i + 1; j < N; ++j) { for (int k = j + 1; k < N; ++k) { one.clear(), two.clear(), three.clear(); for (auto u : mask) { int x = lightest(inv[u], i, j, k); (x == i ? one : (x == j ? two : three)).push_back(u); } if (solve(one, remain - 1) && solve(two, remain - 1) && solve(three, remain - 1)) { compare[mask] = {i, j, k, -1}; return true; } one.clear(), two.clear(), three.clear(); for (auto u : mask) { int x = heaviest(inv[u], i, j, k); (x == i ? one : (x == j ? two : three)).push_back(u); } if (solve(one, remain - 1) && solve(two, remain - 1) && solve(three, remain - 1)) { compare[mask] = {i, j, k, -2}; return true; } one.clear(), two.clear(), three.clear(); for (auto u : mask) { int x = median(inv[u], i, j, k); (x == i ? one : (x == j ? two : three)).push_back(u); } if (solve(one, remain - 1) && solve(two, remain - 1) && solve(three, remain - 1)) { compare[mask] = {i, j, k, -3}; return true; } for (int l = 0; l < N; ++l) { if (l != i && l != j && l != k) { one.clear(), two.clear(), three.clear(); for (auto u : mask) { int x = next(inv[u], i, j, k, l); (x == i ? one : (x == j ? two : three)).push_back(u); } if (solve(one, remain - 1) && solve(two, remain - 1) && solve(three, remain - 1)) { compare[mask] = {i, j, k, l}; return true; } } } } } } return false; } void init(int t) { vector<int> temp(N); iota(temp.begin(), temp.end(), 0); for (int i = 0; i < M; ++i) { perm[i] = temp; inv[i].resize(6); for (int j = 0; j < N; ++j) { inv[i][perm[i][j]] = j; } next_permutation(temp.begin(), temp.end()); } vector<int> mask(M); iota(mask.begin(), mask.end(), 0); solve(mask, 6); } void orderCoins() { vector<int> mask(M); iota(mask.begin(), mask.end(), 0); while (mask.size() > 1) { auto [i, j, k, l] = compare[mask]; vector<int> new_mask; if (l == -1) { int x = getLightest(i + 1, j + 1, k + 1) - 1; for (auto u : mask) { if (lightest(inv[u], i, j, k) == x) { new_mask.push_back(u); } } } else if (l == -2) { int x = getHeaviest(i + 1, j + 1, k + 1) - 1; for (auto u : mask) { if (heaviest(inv[u], i, j, k) == x) { new_mask.push_back(u); } } } else if (l == -3) { int x = getMedian(i + 1, j + 1, k + 1) - 1; for (auto u : mask) { if (median(inv[u], i, j, k) == x) { new_mask.push_back(u); } } } else { int x = getNextLightest(i + 1, j + 1, k + 1, l + 1) - 1; for (auto u : mask) { if (next(inv[u], i, j, k, l) == x) { new_mask.push_back(u); } } } mask = new_mask; } for (int i = 0; i < N; ++i) { ans[i] = perm[mask[0]][i]; } answer(ans); }

컴파일 시 표준 에러 (stderr) 메시지

scales.cpp: In function 'void init(int)':
scales.cpp:123:15: warning: unused parameter 't' [-Wunused-parameter]
  123 | void init(int t) {
      |           ~~~~^
#Verdict Execution timeMemoryGrader output
Fetching results...