제출 #584749

#제출 시각아이디문제언어결과실행 시간메모리
584749hibiki저울 (IOI15_scales)C++11
0 / 100
6 ms412 KiB
#include "scales.h" #include<bits/stdc++.h> using namespace std; #define pb push_back #define f first #define s second #define sz(x) (int)x.size() #define all(x) x.begin(),x.end() struct query { int a,b,c,d,type; query() {}; query(int a, int b, int c, int d, int type): a(a), b(b), c(c), d(d), type(type) {}; }; vector<vector<int> > all; vector<query> ask; int fi_median(int a,int b,int c) { if(max({a, b, c}) != a && min({a, b, c}) != a) return a; if(max({a, b, c}) != b && min({a, b, c}) != b) return b; if(max({a, b, c}) != c && min({a, b, c}) != c) return c; exit(-1); return -1; } int fi_next_light(int a,int b,int c,int d) { int ret = 1e9; if(a > d) ret = min(ret, a); if(b > d) ret = min(ret, b); if(c > d) ret = min(ret, c); if(ret == 1e9) ret = min({a, b, c}); return ret; } void init(int T) { vector<int> v; for(int i = 0; i < 6; i++) v.pb(i); do { all.pb(v); } while(next_permutation(all(v))); for(int a = 0; a < 6; a++) for(int b = a + 1; b < 6; b++) for(int c = b + 1; c < 6; c++) { ask.pb(query(a, b, c, 0, 0)); ask.pb(query(a, b, c, 0, 1)); ask.pb(query(a, b, c, 0, 2)); for(int d = 0; d < 6; d++) { if(a == d || b == d || c == d) continue; ask.pb({a, b, c, d, 3}); } } } void orderCoins() { vector<vector<int> > pos = all; while(1) { if(sz(pos) == 1) { int ans[6]; for(int i = 0; i < 6; i++) ans[(*pos.begin())[i]] = i + 1; return ; } query best; int val = 1e9; for(auto cask: ask) { if(cask.type == 0) { int ta = 0, tb = 0, tc = 0; for(auto nw: pos) { if(max({nw[cask.a], nw[cask.b], nw[cask.c]}) == nw[cask.a]) ta++; if(max({nw[cask.a], nw[cask.b], nw[cask.c]}) == nw[cask.b]) tb++; if(max({nw[cask.a], nw[cask.b], nw[cask.c]}) == nw[cask.c]) tc++; } int mx = max({ta, tb, tc}); if(mx < val) val = mx, best = cask; } else if(cask.type == 1) { int ta = 0, tb = 0, tc = 0; for(auto nw: pos) { if(min({nw[cask.a], nw[cask.b], nw[cask.c]}) == nw[cask.a]) ta++; if(min({nw[cask.a], nw[cask.b], nw[cask.c]}) == nw[cask.b]) tb++; if(min({nw[cask.a], nw[cask.b], nw[cask.c]}) == nw[cask.c]) tc++; } int mx = max({ta, tb, tc}); if(mx < val) val = mx, best = cask; } else if(cask.type == 2) { int ta = 0, tb = 0, tc = 0; for(auto nw: pos) { if(fi_median(nw[cask.a], nw[cask.b], nw[cask.c]) == nw[cask.a]) ta++; if(fi_median(nw[cask.a], nw[cask.b], nw[cask.c]) == nw[cask.b]) tb++; if(fi_median(nw[cask.a], nw[cask.b], nw[cask.c]) == nw[cask.c]) tc++; } int mx = max({ta, tb, tc}); if(mx < val) val = mx, best = cask; } else { int ta = 0, tb = 0, tc = 0; for(auto nw: pos) { if(fi_next_light(nw[cask.a], nw[cask.b], nw[cask.c], nw[cask.d]) == nw[cask.a]) ta++; if(fi_next_light(nw[cask.a], nw[cask.b], nw[cask.c], nw[cask.d]) == nw[cask.b]) tb++; if(fi_next_light(nw[cask.a], nw[cask.b], nw[cask.c], nw[cask.d]) == nw[cask.c]) tc++; } int mx = max({ta, tb, tc}); if(mx < val) val = mx, best = cask; } } vector<vector<int> > next; if(best.type == 0) { int ret = getHeaviest(best.a + 1, best.b + 1, best.c + 1); int ty; if(ret == best.a + 1) ty = 1; if(ret == best.b + 1) ty = 2; if(ret == best.c + 1) ty = 3; for(auto nw: pos) { if(ty == 1 && max({nw[best.a], nw[best.b], nw[best.c]}) == nw[best.a]) next.pb(nw); if(ty == 2 && max({nw[best.a], nw[best.b], nw[best.c]}) == nw[best.b]) next.pb(nw); if(ty == 3 && max({nw[best.a], nw[best.b], nw[best.c]}) == nw[best.c]) next.pb(nw); } } else if(best.type == 1) { int ret = getLightest(best.a + 1, best.b + 1, best.c + 1); int ty; if(ret == best.a + 1) ty = 1; if(ret == best.b + 1) ty = 2; if(ret == best.c + 1) ty = 3; for(auto nw: pos) { if(ty == 1 && min({nw[best.a], nw[best.b], nw[best.c]}) == nw[best.a]) next.pb(nw); if(ty == 2 && min({nw[best.a], nw[best.b], nw[best.c]}) == nw[best.b]) next.pb(nw); if(ty == 3 && min({nw[best.a], nw[best.b], nw[best.c]}) == nw[best.c]) next.pb(nw); } } else if(best.type == 2) { int ret = getMedian(best.a + 1, best.b + 1, best.c + 1); int ty; if(ret == best.a + 1) ty = 1; if(ret == best.b + 1) ty = 2; if(ret == best.c + 1) ty = 3; for(auto nw: pos) { if(ty == 1 && fi_median(nw[best.a], nw[best.b], nw[best.c]) == nw[best.a]) next.pb(nw); if(ty == 2 && fi_median(nw[best.a], nw[best.b], nw[best.c]) == nw[best.b]) next.pb(nw); if(ty == 3 && fi_median(nw[best.a], nw[best.b], nw[best.c]) == nw[best.c]) next.pb(nw); } } else { int ret = getNextLightest(best.a + 1, best.b + 1, best.c + 1, best.d + 1); int ty; if(ret == best.a + 1) ty = 1; if(ret == best.b + 1) ty = 2; if(ret == best.c + 1) ty = 3; for(auto nw: pos) { if(ty == 1 && fi_next_light(nw[best.a], nw[best.b], nw[best.c], nw[best.d]) == nw[best.a]) next.pb(nw); if(ty == 2 && fi_next_light(nw[best.a], nw[best.b], nw[best.c], nw[best.d]) == nw[best.b]) next.pb(nw); if(ty == 3 && fi_next_light(nw[best.a], nw[best.b], nw[best.c], nw[best.d]) == nw[best.c]) next.pb(nw); } } swap(pos, next); } }

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

scales.cpp: In constructor 'query::query(int, int, int, int, int)':
scales.cpp:15:43: warning: declaration of 'type' shadows a member of 'query' [-Wshadow]
   15 |     query(int a, int b, int c, int d, int type): a(a), b(b), c(c), d(d), type(type) {};
      |                                       ~~~~^~~~
scales.cpp:13:17: note: shadowed declaration is here
   13 |     int a,b,c,d,type;
      |                 ^~~~
scales.cpp:15:36: warning: declaration of 'd' shadows a member of 'query' [-Wshadow]
   15 |     query(int a, int b, int c, int d, int type): a(a), b(b), c(c), d(d), type(type) {};
      |                                ~~~~^
scales.cpp:13:15: note: shadowed declaration is here
   13 |     int a,b,c,d,type;
      |               ^
scales.cpp:15:29: warning: declaration of 'c' shadows a member of 'query' [-Wshadow]
   15 |     query(int a, int b, int c, int d, int type): a(a), b(b), c(c), d(d), type(type) {};
      |                         ~~~~^
scales.cpp:13:13: note: shadowed declaration is here
   13 |     int a,b,c,d,type;
      |             ^
scales.cpp:15:22: warning: declaration of 'b' shadows a member of 'query' [-Wshadow]
   15 |     query(int a, int b, int c, int d, int type): a(a), b(b), c(c), d(d), type(type) {};
      |                  ~~~~^
scales.cpp:13:11: note: shadowed declaration is here
   13 |     int a,b,c,d,type;
      |           ^
scales.cpp:15:15: warning: declaration of 'a' shadows a member of 'query' [-Wshadow]
   15 |     query(int a, int b, int c, int d, int type): a(a), b(b), c(c), d(d), type(type) {};
      |           ~~~~^
scales.cpp:13:9: note: shadowed declaration is here
   13 |     int a,b,c,d,type;
      |         ^
scales.cpp: In constructor 'query::query(int, int, int, int, int)':
scales.cpp:15:43: warning: declaration of 'type' shadows a member of 'query' [-Wshadow]
   15 |     query(int a, int b, int c, int d, int type): a(a), b(b), c(c), d(d), type(type) {};
      |                                       ~~~~^~~~
scales.cpp:13:17: note: shadowed declaration is here
   13 |     int a,b,c,d,type;
      |                 ^~~~
scales.cpp:15:36: warning: declaration of 'd' shadows a member of 'query' [-Wshadow]
   15 |     query(int a, int b, int c, int d, int type): a(a), b(b), c(c), d(d), type(type) {};
      |                                ~~~~^
scales.cpp:13:15: note: shadowed declaration is here
   13 |     int a,b,c,d,type;
      |               ^
scales.cpp:15:29: warning: declaration of 'c' shadows a member of 'query' [-Wshadow]
   15 |     query(int a, int b, int c, int d, int type): a(a), b(b), c(c), d(d), type(type) {};
      |                         ~~~~^
scales.cpp:13:13: note: shadowed declaration is here
   13 |     int a,b,c,d,type;
      |             ^
scales.cpp:15:22: warning: declaration of 'b' shadows a member of 'query' [-Wshadow]
   15 |     query(int a, int b, int c, int d, int type): a(a), b(b), c(c), d(d), type(type) {};
      |                  ~~~~^
scales.cpp:13:11: note: shadowed declaration is here
   13 |     int a,b,c,d,type;
      |           ^
scales.cpp:15:15: warning: declaration of 'a' shadows a member of 'query' [-Wshadow]
   15 |     query(int a, int b, int c, int d, int type): a(a), b(b), c(c), d(d), type(type) {};
      |           ~~~~^
scales.cpp:13:9: note: shadowed declaration is here
   13 |     int a,b,c,d,type;
      |         ^
scales.cpp: In constructor 'query::query(int, int, int, int, int)':
scales.cpp:15:43: warning: declaration of 'type' shadows a member of 'query' [-Wshadow]
   15 |     query(int a, int b, int c, int d, int type): a(a), b(b), c(c), d(d), type(type) {};
      |                                       ~~~~^~~~
scales.cpp:13:17: note: shadowed declaration is here
   13 |     int a,b,c,d,type;
      |                 ^~~~
scales.cpp:15:36: warning: declaration of 'd' shadows a member of 'query' [-Wshadow]
   15 |     query(int a, int b, int c, int d, int type): a(a), b(b), c(c), d(d), type(type) {};
      |                                ~~~~^
scales.cpp:13:15: note: shadowed declaration is here
   13 |     int a,b,c,d,type;
      |               ^
scales.cpp:15:29: warning: declaration of 'c' shadows a member of 'query' [-Wshadow]
   15 |     query(int a, int b, int c, int d, int type): a(a), b(b), c(c), d(d), type(type) {};
      |                         ~~~~^
scales.cpp:13:13: note: shadowed declaration is here
   13 |     int a,b,c,d,type;
      |             ^
scales.cpp:15:22: warning: declaration of 'b' shadows a member of 'query' [-Wshadow]
   15 |     query(int a, int b, int c, int d, int type): a(a), b(b), c(c), d(d), type(type) {};
      |                  ~~~~^
scales.cpp:13:11: note: shadowed declaration is here
   13 |     int a,b,c,d,type;
      |           ^
scales.cpp:15:15: warning: declaration of 'a' shadows a member of 'query' [-Wshadow]
   15 |     query(int a, int b, int c, int d, int type): a(a), b(b), c(c), d(d), type(type) {};
      |           ~~~~^
scales.cpp:13:9: note: shadowed declaration is here
   13 |     int a,b,c,d,type;
      |         ^
scales.cpp: In function 'void init(int)':
scales.cpp:44:15: warning: unused parameter 'T' [-Wunused-parameter]
   44 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:71:17: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   71 |             int ans[6];
      |                 ^~~
scales.cpp:164:14: warning: 'best.query::type' may be used uninitialized in this function [-Wmaybe-uninitialized]
  164 |         else if(best.type == 2)
      |              ^~
scales.cpp:138:34: warning: 'best.query::a' may be used uninitialized in this function [-Wmaybe-uninitialized]
  138 |             int ret = getHeaviest(best.a + 1, best.b + 1, best.c + 1);
      |                       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:138:34: warning: 'best.query::b' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:138:34: warning: 'best.query::c' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:187:90: warning: 'best.query::d' may be used uninitialized in this function [-Wmaybe-uninitialized]
  187 |                 if(ty == 1 && fi_next_light(nw[best.a], nw[best.b], nw[best.c], nw[best.d]) == nw[best.a]) next.pb(nw);
      |                                                                                          ^
scales.cpp:188:28: warning: 'ty' may be used uninitialized in this function [-Wmaybe-uninitialized]
  188 |                 if(ty == 2 && fi_next_light(nw[best.a], nw[best.b], nw[best.c], nw[best.d]) == nw[best.b]) next.pb(nw);
scales.cpp:174:28: warning: 'ty' may be used uninitialized in this function [-Wmaybe-uninitialized]
  174 |                 if(ty == 2 && fi_median(nw[best.a], nw[best.b], nw[best.c]) == nw[best.b]) next.pb(nw);
scales.cpp:161:28: warning: 'ty' may be used uninitialized in this function [-Wmaybe-uninitialized]
  161 |                 if(ty == 3 && min({nw[best.a], nw[best.b], nw[best.c]}) == nw[best.c]) next.pb(nw);
scales.cpp:147:28: warning: 'ty' may be used uninitialized in this function [-Wmaybe-uninitialized]
  147 |                 if(ty == 3 && max({nw[best.a], nw[best.b], nw[best.c]}) == nw[best.c]) next.pb(nw);
#Verdict Execution timeMemoryGrader output
Fetching results...