제출 #287433

#제출 시각아이디문제언어결과실행 시간메모리
287433Kastanda저울 (IOI15_scales)C++11
0 / 100
1116 ms236572 KiB
// M #include<bits/stdc++.h> #include "scales.h" #define pb push_back using namespace std; const int K = 6, MXN = 1e7, INF = 1e4; int CalcHeaviest(vector < vector < int > > &, int, int, int, int, int); int CalcLightest(vector < vector < int > > &, int, int, int, int, int); int CalcMedian(vector < vector < int > > &, int, int, int, int, int); int CalcNext(vector < vector < int > > &, int, int, int, int, int, int); vector < vector < int > > DoHeaviest(vector < vector < int > > &now, int a, int b, int c, int t) { vector < vector < int > > tobe; for (auto vec : now) if (vec[a] <= vec[t] && vec[b] <= vec[t] && vec[c] <= vec[t]) tobe.pb(vec); return tobe; } vector < vector < int > > DoLightest(vector < vector < int > > &now, int a, int b, int c, int t) { vector < vector < int > > tobe; for (auto &vec : now) if (vec[a] >= vec[t] && vec[b] >= vec[t] && vec[c] >= vec[t]) tobe.pb(vec); return tobe; } vector < vector < int > > DoMedian(vector < vector < int > > &now, int a, int b, int c, int t) { if (a == t) a = c; else if (b == t) b = c; assert(a != t && b != t && a != b); vector < vector < int > > tobe; for (auto &vec : now) if ((vec[a] < vec[t] && vec[b] > vec[t]) || (vec[a] > vec[t] && vec[b] < vec[t])) tobe.pb(vec); return tobe; } vector < vector < int > > DoNext(vector < vector < int > > &now, int a, int b, int c, int d, int t) { vector < vector < int > > tobe; for (auto &vec : now) { vector < pair < int , int > > tmp; tmp.pb({vec[a], a}); tmp.pb({vec[b], b}); tmp.pb({vec[c], c}); sort(tmp.begin(), tmp.end()); int lb = lower_bound(tmp.begin(), tmp.end(), make_pair(vec[d], d)) - tmp.begin(); if (lb == 3) lb = 0; if (tmp[lb].second == t) tobe.pb(vec); } return tobe; } int ts, Rs[MXN]; vector < int > VM[MXN]; map < vector < vector < int > > , int > MP, PM[K + 1]; vector < vector < int > > All; int DEF_TRN = 4; int Solve(vector < vector < int > > now, int isFirstMove = 0, int TRN = DEF_TRN) { if (PM[TRN].count(now)) return Rs[PM[TRN][now]]; int atleast = 0, nwsz = (int)now.size(); while (nwsz > 1) nwsz = (nwsz + 2) / 3, atleast ++; if (atleast > TRN) return INF; int id = ++ ts; PM[TRN][now] = id; Rs[id] = INF; if ((int)now.size() <= 1) return Rs[id] = 0; int MnMove = INF; vector < int > VMove; { for (int a = 0; a < K; a ++) for (int b = a + 1; b < K; b ++) for (int c = b + 1; c < K; c ++) { if (MnMove < TRN) continue; for (int d = 0; d < K; d ++) if (d != a && d != b && d != c) { int mx = CalcNext(now, a, b, c, d, a, TRN); mx = max(mx, CalcNext(now, a, b, c, d, b, TRN)); mx = max(mx, CalcNext(now, a, b, c, d, c, TRN)); if (mx < MnMove) { MnMove = mx; VMove = {3, a, b, c, d}; } } if (isFirstMove && (a != 0 || b != 1 || c != 2)) continue; int mx = CalcHeaviest(now, a, b, c, a, TRN); mx = max(mx, CalcHeaviest(now, a, b, c, b, TRN)); mx = max(mx, CalcHeaviest(now, a, b, c, c, TRN)); if (mx < MnMove) { MnMove = mx; VMove = {0, a, b, c}; } mx = CalcLightest(now, a, b, c, a, TRN); mx = max(mx, CalcLightest(now, a, b, c, b, TRN)); mx = max(mx, CalcLightest(now, a, b, c, c, TRN)); if (mx < MnMove) { MnMove = mx; VMove = {1, a, b, c}; } mx = CalcMedian(now, a, b, c, a, TRN); mx = max(mx, CalcMedian(now, a, b, c, b, TRN)); mx = max(mx, CalcMedian(now, a, b, c, c, TRN)); if (mx < MnMove) { MnMove = mx; VMove = {2, a, b, c}; } } } if (MnMove + 1 > TRN) return INF; Rs[id] = MnMove + 1; VM[id] = VMove; return Rs[id]; } int CalcHeaviest(vector < vector < int > > &now, int a, int b, int c, int t, int TRN) { auto tobe = DoHeaviest(now, a, b, c, t); if (tobe == now) return INF; return Solve(tobe, 0, TRN - 1); } int CalcLightest(vector < vector < int > > &now, int a, int b, int c, int t, int TRN) { auto tobe = DoLightest(now, a, b, c, t); if (tobe == now) return INF; return Solve(tobe, 0, TRN - 1); } int CalcMedian(vector < vector < int > > &now, int a, int b, int c, int t, int TRN) { auto tobe = DoMedian(now, a, b, c, t); if (tobe == now) return INF; return Solve(tobe, 0, TRN - 1); } int CalcNext(vector < vector < int > > &now, int a, int b, int c, int d, int t, int TRN) { auto tobe = DoNext(now, a, b, c, d, t); if (tobe == now) return INF; return Solve(tobe, 0, TRN - 1); } void init(int T) { ts = 0; All.clear(); vector < int > P(K); iota(P.begin(), P.end(), 0); do { All.pb(P); } while (next_permutation(P.begin(), P.end())); } void orderCoins() { for (int i = 0; i <= K; i ++) PM[i].clear(); ts = 0; vector < vector < int > > now = All; { int lt = getLightest(0 + 1, 1 + 1, 2 + 1) - 1; now = DoLightest(now, 0, 1, 2, lt); int md = getMedian(3 + 1, 4 + 1, 5 + 1) - 1; now = DoMedian(now, 3, 4, 5, md); cerr << Solve(now, 1, 4) << endl; } int TRN = 4; while (now.size() > 1) { assert(PM[TRN].count(now)); int id = PM[TRN][now]; TRN --; vector < int > VMove = VM[id]; if (VMove[0] == 0) { int hv = getHeaviest(VMove[1] + 1, VMove[2] + 1, VMove[3] + 1) - 1; now = DoHeaviest(now, VMove[1], VMove[2], VMove[3], hv); continue; } else if (VMove[0] == 1) { int lt = getLightest(VMove[1] + 1, VMove[2] + 1, VMove[3] + 1) - 1; now = DoLightest(now, VMove[1], VMove[2], VMove[3], lt); continue; } else if (VMove[0] == 2) { int md = getMedian(VMove[1] + 1, VMove[2] + 1, VMove[3] + 1) - 1; now = DoMedian(now, VMove[1], VMove[2], VMove[3], md); continue; } else if (VMove[0] == 3) { int nx = getNextLightest(VMove[1] + 1, VMove[2] + 1, VMove[3] + 1, VMove[4] + 1) - 1; now = DoNext(now, VMove[1], VMove[2], VMove[3], VMove[4], nx); continue; } assert(0); } int W[6]; assert((int)now.size() == 1); vector < int > rs = now[0]; for (int i = 0; i < K; i ++) W[rs[i]] = i + 1; answer(W); }

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

scales.cpp: In function 'std::vector<std::vector<int> > DoNext(std::vector<std::vector<int> >&, int, int, int, int, int)':
scales.cpp:50:84: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   50 |                 int lb = lower_bound(tmp.begin(), tmp.end(), make_pair(vec[d], d)) - tmp.begin();
      |                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:171:15: warning: unused parameter 'T' [-Wunused-parameter]
  171 | void init(int T)
      |           ~~~~^
#Verdict Execution timeMemoryGrader output
Fetching results...