Submission #584749

#	Time	Username	Problem	Language	Result	Execution time	Memory
584749		hibiki	Scales (IOI15_scales)	C++11	0 / 100	6 ms	412 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;
            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);
    }
}

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: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);

• Subtask 1: 0 / 100