제출 #830793

#제출 시각아이디문제언어결과실행 시간메모리
830793drdilyor저울 (IOI15_scales)C++17
71.43 / 100
12 ms552 KiB
#include<bits/stdc++.h> #include "scales.h" using namespace std; using ll = long long; #define sz(x) int((x).size()) ll pw3[30]; const int n = 6; const int inf = 1e9; using st = array<int, 6>; using op = tuple<int,int,int,int,int>; map<vector<st>, op> usedop; array<vector<st>, 3> getNext(vector<st> cur, op op) { auto [t, a, b, c, d] = op; array<vector<st>, 3> next{{}}; if (t == 0) { for (auto& i : cur) { int mn = min({i[a], i[b], i[c]}); if (i[a] == mn) next[0].push_back(i); else if (i[b] == mn) next[1].push_back(i); else next[2].push_back(i); } } else if (t == 1) { for (auto& i : cur) { int mx = max({i[a], i[b], i[c]}); if (i[a] == mx) next[0].push_back(i); else if (i[b] == mx) next[1].push_back(i); else next[2].push_back(i); } } else { for (auto& i : cur) { array cur{i[a], i[b], i[c]}; sort(cur.begin(), cur.end()); if (i[a] == cur[1]) next[0].push_back(i); else if (i[b] == cur[1]) next[1].push_back(i); else next[2].push_back(i); } } return next; } int cost(array<vector<st>, 3> pos) { return max({pos[0].size(), pos[1].size(), pos[2].size()}); } int rec(vector<st> pos, int qleft) { if (pw3[qleft] < sz(pos)) return false; if (pos.size() <= 1) return true; array<vector<st>, 3> best; int bestx = inf; op bestq; auto tryAccept =[&](op op) { auto next = getNext(pos, op); int mx = max({next[0].size(), next[1].size(), next[2].size()}); if (mx < bestx) { bestx = mx; best = next; bestq = op; } }; for (int a = 0; a < n; a++) { for (int b = a+1; b < n; b++) { for (int c = b+1; c < n; c++) { tryAccept({0, a, b, c, -1}); tryAccept({1, a, b, c, -1}); tryAccept({2, a, b, c, -1}); } } } assert(bestx != inf); if (!rec(best[0], qleft-1)) return false; if (!rec(best[1], qleft-1)) return false; if (!rec(best[2], qleft-1)) return false; usedop[pos] = bestq; return true; } void init(int T) { pw3[0] = 1; for (int i = 1; i < 30; i++) pw3[i] = pw3[i-1] * 3; vector<st> pos; st cur; iota(cur.begin(), cur.end(), 0); do { pos.push_back(cur); } while (next_permutation(cur.begin(), cur.end())); rec(pos, 8); // cout << rec(pos, 8) << endl; } void orderCoins() { vector<st> pos;{ st cur; iota(cur.begin(), cur.end(), 0); do { pos.push_back(cur); } while (next_permutation(cur.begin(), cur.end()));} while (pos.size() > 1) { // cout << "pos.size()=" << pos.size() << endl; assert(usedop.count(pos)); auto op = usedop[pos]; auto[t, a, b, c, d] = op; auto next = getNext(pos, op); a++;b++;c++; if (t == 0) { int ans = getLightest(a, b, c); if (ans == a) pos = next[0]; if (ans == b) pos = next[1]; if (ans == c) pos = next[2]; } else if (t == 1) { int ans = getHeaviest(a, b, c); if (ans == a) pos = next[0]; if (ans == b) pos = next[1]; if (ans == c) pos = next[2]; } else { int ans = getMedian(a, b, c); if (ans == a) pos = next[0]; if (ans == b) pos = next[1]; if (ans == c) pos = next[2]; } } int w[6]; for (int i = 0; i < 6; i++) { w[pos[0][i]] = i+1; } answer(w); }

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

scales.cpp: In function 'std::array<std::vector<std::array<int, 6> >, 3> getNext(std::vector<std::array<int, 6> >, op)':
scales.cpp:16:49: warning: declaration of 'op' shadows a global declaration [-Wshadow]
   16 | array<vector<st>, 3> getNext(vector<st> cur, op op) {
      |                                              ~~~^~
scales.cpp:12:7: note: shadowed declaration is here
   12 | using op = tuple<int,int,int,int,int>;
      |       ^~
scales.cpp:41:19: warning: declaration of 'array<...auto...> cur' shadows a parameter [-Wshadow]
   41 |             array cur{i[a], i[b], i[c]};
      |                   ^~~
scales.cpp:16:41: note: shadowed declaration is here
   16 | array<vector<st>, 3> getNext(vector<st> cur, op op) {
      |                              ~~~~~~~~~~~^~~
scales.cpp: In function 'int cost(std::array<std::vector<std::array<int, 6> >, 3>)':
scales.cpp:55:15: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
   55 |     return max({pos[0].size(), pos[1].size(), pos[2].size()});
      |            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp: In lambda function:
scales.cpp:65:28: warning: declaration of 'op' shadows a global declaration [-Wshadow]
   65 |     auto tryAccept =[&](op op) {
      |                         ~~~^~
scales.cpp:12:7: note: shadowed declaration is here
   12 | using op = tuple<int,int,int,int,int>;
      |       ^~
scales.cpp:67:21: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
   67 |         int mx = max({next[0].size(), next[1].size(), next[2].size()});
      |                  ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:94:15: warning: unused parameter 'T' [-Wunused-parameter]
   94 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:121:14: warning: declaration of 'op' shadows a global declaration [-Wshadow]
  121 |         auto op = usedop[pos];
      |              ^~
scales.cpp:12:7: note: shadowed declaration is here
   12 | using op = tuple<int,int,int,int,int>;
      |       ^~
#Verdict Execution timeMemoryGrader output
Fetching results...