제출 #520517

#제출 시각아이디문제언어결과실행 시간메모리
520517silverfish저울 (IOI15_scales)C++17
71.43 / 100
54 ms580 KiB
#include "scales.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define ar array const int INF = 10000000; int nextl(int a, int b, int c, int d, vector<int> &ind) { int al = 1; a--; b--; c--; d--; if (ind[a] > ind[d] || ind[b] > ind[d] || ind[c] > ind[d]) al = 0; if (al == 1) { if (ind[a] < ind[b] && ind[a] < ind[c])return a + 1; if (ind[b] < ind[a] && ind[b] < ind[c])return b + 1; return c + 1; } if (ind[a] > ind[d]) if ((ind[a] < ind[b] || ind[b] < ind[d]) && (ind[a] < ind[c]||ind[c]<ind[d]))return a + 1; if(ind[b] > ind[d]) if((ind[b]<ind[a]||ind[a]<ind[d])&&(ind[b]<ind[c]||ind[c]<ind[d]))return b + 1; return c + 1; } int mid(int a, int b, int c, vector<int> &ind) { a--; b--; c--; if (ind[b] < ind[a] && ind[a] < ind[c])return a + 1; if (ind[c] < ind[a] && ind[a] < ind[b])return a + 1; if (ind[a] < ind[b] && ind[b] < ind[c])return b + 1; if (ind[c] < ind[b] && ind[b] < ind[a])return b + 1; return c + 1; } int heavy(int a, int b, int c, vector<int> &ind) { a--; b--; c--; if (ind[a] > ind[b] && ind[a] > ind[c])return a + 1; if (ind[b] > ind[a] && ind[b] > ind[c])return b + 1; return c + 1; } int light(int a, int b, int c, vector<int> &ind) { a--; b--; c--; if(ind[a]<ind[b]&&ind[a]<ind[c]) return a + 1; if(ind[b]<ind[a]&&ind[b]<ind[c]) return b + 1; return c + 1; } struct query{ // 1 : nextl // 2 : light // 3 : mid // 4 : heavy int t; int a, b, c, d; int execute(int cp){ vector<int> p(6), ind(6); for(int i = 5; i >= 0; --i) p[i]=(cp%10), cp/=10; for(int i = 0; i < 6; ++i) ind[p[i]-1] = i; switch(t){ case 1: return nextl(a,b,c,d,ind); case 2: return light(a,b,c,ind); case 3: return mid(a,b,c,ind); case 4: return heavy(a,b,c,ind); } return -1; } int execute_real(){ switch(t){ case 1: return getNextLightest(a,b,c,d); case 2: return getLightest(a,b,c); case 3: return getMedian(a,b,c); case 4: return getHeaviest(a,b,c); } return -1; } }; struct node{ query cur; ar<node*, 7> nxt; int ansp=0; }; vector<query> allq; void solve(node* rt, vector<int> p){ if(p.size() == 1){ rt->ansp = p[0]; return; } int mn = INF; query best; for(auto q : allq){ int cnt[7] = {0}; for(int cp : p) ++cnt[q.execute(cp)]; int mx = 0; for(int i = 1; i <= 6; ++i) mx = max(mx, cnt[i]); if(mx < mn){ mn = mx; best = q; } } rt->cur = best; vector<int> np[7]; for(int cp : p) np[best.execute(cp)].pb(cp); for(int i = 1; i <= 6; ++i){ if(np[i].size()){ rt->nxt[i] = new node; solve(rt->nxt[i], np[i]); }else rt->nxt[i] = nullptr; } } vector<int> allp; node* rt = new node; void gen_all(){ for(int i=1;i<=6;++i) for(int j=i+1;j<=6;++j) for(int k=j+1;k<=6;++k){ allq.pb({2,i,j,k}); allq.pb({3,i,j,k}); allq.pb({4,i,j,k}); } for(int i = 1; i <= 6; ++i) for(int j = 1; j <= 6; ++j){ if(j==i) continue; for(int k = j+1; k <= 6; ++k){ if(k==i) continue; for(int a = k+1; a <= 6; ++a){ if(a==i) continue; allq.pb({1,i,j,k,a}); } } } vector<int> p = {1,2,3,4,5,6}; do{ int v=0, mul = 1; for(int i = 5; i >= 0; --i){ v += p[i]*mul; mul *= 10; } allp.pb(v); }while(next_permutation(p.begin(), p.end())); return; } void init(int T) { gen_all(); solve(rt, allp); return; } void orderCoins() { node* crt = rt; while(!crt->ansp){ int v = crt->cur.execute_real(); crt = crt->nxt[v]; } int ans[6], cp = crt->ansp; for(int i = 5; i >= 0; --i) ans[i]=(cp%10), cp/=10; answer(ans); return; }

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

scales.cpp: In function 'void gen_all()':
scales.cpp:130:20: warning: missing initializer for member 'query::d' [-Wmissing-field-initializers]
  130 |   allq.pb({2,i,j,k});
      |                    ^
scales.cpp:131:20: warning: missing initializer for member 'query::d' [-Wmissing-field-initializers]
  131 |   allq.pb({3,i,j,k});
      |                    ^
scales.cpp:132:20: warning: missing initializer for member 'query::d' [-Wmissing-field-initializers]
  132 |   allq.pb({4,i,j,k});
      |                    ^
scales.cpp: In function 'void init(int)':
scales.cpp:158:15: warning: unused parameter 'T' [-Wunused-parameter]
  158 | void init(int T) {
      |           ~~~~^
#Verdict Execution timeMemoryGrader output
Fetching results...