Submission #584840

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

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++)
                {
                    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 ;
        }
 
        vector<query> vbest;
        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;
                  	vbest.clear();
                  	vbest.pb(cask);
                }    
              	else if(mx == val)
                {
                  	vbest.pb(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;
                  	vbest.clear();
                  	vbest.pb(cask);
                }    
              	else if(mx == val)
                {
                  	vbest.pb(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;
                  	vbest.clear();
                  	vbest.pb(cask);
                }    
              	else if(mx == val)
                {
                  	vbest.pb(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;
                  	vbest.clear();
                  	vbest.pb(cask);
                }    
              	else if(mx == val)
                {
                  	vbest.pb(cask);
                }
            }
        }
 		
      	query best = vbest[(rand()) % sz(vbest)];
        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:72:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   72 |             for(int i = 0; i < 6; i++)
      |             ^~~
scales.cpp:74:11: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   74 |           answer(ans);
      |           ^~~~~~

• Subtask 1: 72.321429 / 100