Submission #584839

#	Time	Username	Problem	Language	Result	Execution time	Memory
584839		hibiki	Scales (IOI15_scales)	C++11	100 / 100	84 ms	404 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

scales

#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++) for(int a = 0; a < 6; a++) for(int b = a + 1; b < 6; b++) for(int c = b + 1; c < 6; c++) { 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; answer(ans); 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) - 1; for(auto nw: pos) { if(max({nw[best.a], nw[best.b], nw[best.c]}) == nw[ret]) next.pb(nw); } } else if(best.type == 1) { int ret = getLightest(best.a + 1, best.b + 1, best.c + 1) - 1; for(auto nw: pos) { if(min({nw[best.a], nw[best.b], nw[best.c]}) == nw[ret]) next.pb(nw); } } else if(best.type == 2) { int ret = getMedian(best.a + 1, best.b + 1, best.c + 1) - 1; for(auto nw: pos) { if(fi_median(nw[best.a], nw[best.b], nw[best.c]) == nw[ret]) next.pb(nw); } } else { int ret = getNextLightest(best.a + 1, best.b + 1, best.c + 1, best.d + 1) - 1; for(auto nw: pos) { if(fi_next_light(nw[best.a], nw[best.b], nw[best.c], nw[best.d]) == nw[ret]) next.pb(nw); } } swap(pos, next); } }

Compilation message (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:75:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   75 |             for(int i = 0; i < 6; i++)
      |             ^~~
scales.cpp:77:11: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   77 |           answer(ans);
      |           ^~~~~~
scales.cpp:142:34: warning: 'best.query::a' may be used uninitialized in this function [-Wmaybe-uninitialized]
  142 |             int ret = getHeaviest(best.a + 1, best.b + 1, best.c + 1) - 1;
      |                       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:142:34: warning: 'best.query::b' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:142:34: warning: 'best.query::c' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:169:79: warning: 'best.query::d' may be used uninitialized in this function [-Wmaybe-uninitialized]
  169 |                 if(fi_next_light(nw[best.a], nw[best.b], nw[best.c], nw[best.d]) == nw[ret]) next.pb(nw);
      |                                                                               ^
scales.cpp:156:14: warning: 'best.query::type' may be used uninitialized in this function [-Wmaybe-uninitialized]
  156 |         else if(best.type == 2)
      |              ^~

Subtask 1100 / 100

#	Verdict	Execution time	Memory	Grader output
Fetching results...