Submission #1213004

#TimeUsernameProblemLanguageResultExecution timeMemory
1213004LemserScales (IOI15_scales)C++20
71.43 / 100
216 ms520 KiB
#include "scales.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; using lld = long double; using ii = pair<int,int>; using pll = pair<ll, ll>; using vi = vector<int>; using vll = vector<ll>; using vii = vector<ii>; using vpll = vector<pll>; using vlld = vector<lld>; #define all(x) x.begin(),x.end() #define lsb(x) x&(-x) #define gcd(a,b) __gcd(a,b) #define sz(x) (int)x.size() #define mp make_pair #define pb push_back #define fi first #define se second #define fls cout.flush() #define fore(i, l, r) for (auto i = l; i < r; i++) #define fo(i, n) fore (i, 0, n) #define forex(i, r, l) for (auto i = r-1; i >= l; i--) #define ffo(i, n) forex (i, n, 0) bool cmin(ll &a, ll b) { if (b < a) { a=b; return 1; } return 0; } bool cmax(ll &a, ll b) { if (b > a) { a=b; return 1; } return 0; } const ll INF = 1e18; vector<array<ll, 5>> queries; void init(int T) { for (ll a = 1; a <= 6; a++) { for (ll b = a+1; b <= 6; b++) { for (ll c = b+1; c <= 6; c++) { queries.pb({0, a, b, c, -1}); queries.pb({1, a, b, c, -1}); queries.pb({2, a, b, c, -1}); for (ll d =1; d <= 6; d++) { if (a == d || b == d || c == d) continue; queries.pb({3, a, b, c, d}); } } } } } void orderCoins() { vector<vll> pos; vll uax = {1, 2, 3, 4, 5, 6}; do { pos.pb(uax); } while (next_permutation(all(uax))); while (pos.size() > 1) { // cout << pos.size() << '\n'; auto q = queries[0]; ll mn = INF; for (auto [op, a, b, c, d]: queries) { ll cnt[7]{}; for (vll perm: pos) { vll p; ll idx = 0; fo (i, 6) { if (perm[i] != a && perm[i] != b && perm[i] != c && perm[i] != d) continue; if (perm[i] == d) idx = p.size(); p.pb(perm[i]); } if (op == 0) cnt[p[2]]++; else if (op == 1) cnt[p[1]]++; else if (op == 2) cnt[p[0]]++; else cnt[p[(idx+1)%4]]++; } ll x = max({cnt[a], cnt[b], cnt[c]}); if (x < mn) { q = array<ll, 5>{op, a, b, c, d}; mn = x; } } ll x; // if (q[0] == 0) { // x = func(q[0], q[1], q[2], q[3], -1); // } else if (q[0] == 1) { // x = func(q[0], q[1], q[2], q[3], -1); // } else if (q[0] == 2) { // x = func(q[0], q[1], q[2], q[3], -1); // } else { // x = func(q[0], q[1], q[2], q[3], q[4]); // } if (q[0] == 0) { x = getHeaviest(q[1], q[2], q[3]); } else if (q[0] == 1) { x = getMedian(q[1], q[2], q[3]); } else if (q[0] == 2) { x = getLightest(q[1], q[2], q[3]); } else { x = getNextLightest(q[1], q[2], q[3], q[4]); } vector<vll> npos; auto [op, a, b, c, d] = q; for (vll perm: pos) { vll p; ll idx = 0; fo (i, 6) { if (perm[i] != a && perm[i] != b && perm[i] != c && perm[i] != d) continue; if (perm[i] == d) idx = p.size(); p.pb(perm[i]); } ll x2; if (op == 0) x2 = p[2]; else if (op == 1) x2 = p[1]; else if (op == 2) x2 = p[0]; else x2 = p[(idx+1)%4]; if (x == x2) npos.pb(perm); } pos = npos; } int ans[6], d = 0; for (ll i: pos[0]) ans[d++] = i; answer(ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...