제출 #30993

#제출 시각아이디문제언어결과실행 시간메모리
30993kajebiii저울 (IOI15_scales)C++14
0 / 100
113 ms2304 KiB
#include "scales.h" #include <bits/stdc++.h> using namespace std; #define SZ(v) ((int)(v).size()) #define ALL(v) (v).begin(),(v).end() #define one first #define two second typedef long long ll; typedef pair<double, double> pd; typedef pair<int, int> pi; typedef pair<ll, int> pli; typedef pair<ll, ll> pll; typedef pair<ll, pi> plp; typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli; const int INF = 0x3f2f1f0f; const ll LINF = 1ll * INF * INF * 2; static void __checkQuery(int A, int B, int C, int D) { if (D == -1) { if (A < 1 || A > 6 || B < 1 || B > 6 || C < 1 || C > 6) assert(0); if (A == B || B == C || A == C) assert(0); } else { if (A < 1 || A > 6 || B < 1 || B > 6 || C < 1 || C > 6 || D < 1 || D > 6) assert(0); if (A == B || A == C || A == D || B == C || B == D || C == D) assert(0); } } int _getMedian(int A, int B, int C, vector<int> _ind) { __checkQuery(A, B, C, -1); 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 _getHeaviest(int A, int B, int C, vector<int> _ind) { __checkQuery(A, B, C, -1); 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 _getLightest(int A, int B, int C, vector<int> _ind) { __checkQuery(A, B, C, -1); 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 _getNextLightest(int A, int B, int C, int D, vector<int> _ind) { int allLess = 1; __checkQuery(A, B, C, D); A--; B--; C--; D--; if (_ind[A] > _ind[D] || _ind[B] > _ind[D] || _ind[C] > _ind[D]) allLess = 0; if (allLess == 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; } vector<vector<int>> Candi; vector<vector<int>> Qs; vector<int> cntList[10]; int minV = INF; vector<pi> His; map<vector<pi>, int> Mp; bool isCan(int times, vector<int> cd, bool find) { if(times < minV) { minV = times; printf("%d\n", times); } int n = SZ(cd); int cnt = 0; for(int nn=n; nn > 1; nn = (nn+2) / 3, cnt++); if(cnt > times) return false; if(times == 0) { if(find && SZ(cd) > 0) Mp[His] = cd[0]; // for(pi &e : His) printf("[%d %d] ", e.one, e.two); puts(""); return true; } for(int cnt : cntList[6-times]) { vector<int> &v = Qs[cnt]; vector<int> nt[3]; int q = v[0], a = v[1], b = v[2], c = v[3]; int d = -1; if(q == 3) d = v[4]; for(int x : cd) { int res = -1; if(q == 0) res = _getHeaviest(a, b, c, Candi[x]); if(q == 1) res = _getMedian(a, b, c, Candi[x]); if(q == 2) res = _getLightest(a, b, c, Candi[x]); if(q == 3) res = _getNextLightest(a, b, c, d, Candi[x]); for(int k=0; k<3; k++) if(res == v[k+1]) { nt[k].push_back(x); break; } } bool nowCan = true; for(int k=0; k<3; k++) { His.push_back(pi(cnt, k)); bool res = isCan(times-1, nt[k], false); His.pop_back(); if(!res) { nowCan = false; break; } } if(nowCan) { if(times == 6 || find == true) { Mp[His] = cnt; for(int k=0; k<3; k++) { His.push_back(pi(cnt, k)); bool res = isCan(times-1, nt[k], true); His.pop_back(); } } return true; } cnt++; } return false; } void init(int T) { cntList[0] = vector<int>({0}); cntList[1] = vector<int>({58}); cntList[2] = vector<int>({67, 69, 70, 73, 74, 75, 77, 78, 79}); cntList[3] = vector<int>({7, 10, 26, 29, 41, 44, 47, 50, 53, 56, 63, 76}); cntList[4] = vector<int>({3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 27, 28, 31, 34, 48, 49, 51, 52, 83, 84, 85, 92, 93, 94, 105, 106}); cntList[5] = vector<int>({1, 3, 4, 6, 7, 10, 12, 13, 15, 16, 19, 22, 25, 28, 31, 34, 37, 39, 40, 42, 43, 45, 46, 49, 52, 55}); Candi.clear(); int ch[6]; for(int i=0; i<6; i++) ch[i] = i+1; do{ Candi.push_back(vector<int>()); for(int i=0; i<6; i++) Candi.back().push_back(ch[i]); }while(next_permutation(ch, ch+6)); for(int i=0; i<6; i++) ch[i] = (i >= 3); do{ vector<int> list; for(int i=0; i<6; i++) if(ch[i]) list.push_back(i); for(int q=0; q<3; q++) { Qs.push_back(vector<int>()); Qs.back().push_back(q); for(int x : list) Qs.back().push_back(x+1); } }while(next_permutation(ch, ch+6)); for(int i=0; i<6; i++) ch[i] = (i >= 2) + (i == 5); do{ vector<int> list; int d = -1; for(int i=0; i<6; i++) { if(ch[i] == 1) list.push_back(i); if(ch[i] == 2) d = i; } Qs.push_back(vector<int>()); Qs.back().push_back(3); for(int x : list) Qs.back().push_back(x+1); Qs.back().push_back(d+1); }while(next_permutation(ch, ch+6)); // for(vector<int> cd : Candi) {for(int x : cd) printf("%d ", x); puts("");} // for(vector<int> &v : Qs) {for(int x : v) printf("%d ", x); puts("");} vector<int> fs; for(int i=0; i<720; i++) fs.push_back(i); if(isCan(6, fs, false)) puts("YES!"); else puts("NO!"); /* vector<int> all[10]; for(pair<vector<pi>, int> aa : Mp) { for(pi e : aa.one) printf("[%d %d] ", e.one, e.two); puts(""); printf(": %d\n", aa.two); all[SZ(aa.one)].push_back(aa.two); } for(int i=0; i<6; i++) { sort(ALL(all[i])); all[i].erase(unique(ALL(all[i])), all[i].end()); for(int x : all[i]) printf("%d ", x); puts(""); } */ } void orderCoins() { vector<pi> his; for(int i=0; i<6; i++) { int cnt = Mp[his]; vector<int> &v = Qs[cnt]; vector<int> nt[3]; int q = v[0], a = v[1], b = v[2], c = v[3]; int d = -1; if(q == 3) d = v[4]; int res; if(q == 0) res = getHeaviest(a, b, c); if(q == 1) res = getMedian(a, b, c); if(q == 2) res = getLightest(a, b, c); if(q == 3) res = getNextLightest(a, b, c, d); int ix = -1; for(int k=0; k<3; k++) if(res == v[k+1]) ix = k; his.push_back(pi(cnt, ix)); } int ans = Mp[his]; int w[6]; for(int i=0; i<6; i++) w[Candi[ans][i]-1] = i+1; answer(w); }

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

scales.cpp: In function 'bool isCan(int, std::vector<int>, bool)':
scales.cpp:141:13: warning: declaration of 'cnt' shadows a previous local [-Wshadow]
     for(int cnt : cntList[6-times]) {
             ^
scales.cpp:132:9: note: shadowed declaration is here
     int cnt = 0;
         ^
scales.cpp:175:26: warning: unused variable 'res' [-Wunused-variable]
                     bool res = isCan(times-1, nt[k], true);
                          ^
scales.cpp: At global scope:
scales.cpp:186:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T) {
               ^
scales.cpp: In function 'void orderCoins()':
scales.cpp:262:32: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
         for(int k=0; k<3; k++) if(res == v[k+1]) ix = k;
                                ^
#Verdict Execution timeMemoryGrader output
Fetching results...