Submission #788862

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
788862	2023-07-20T16:54:17 Z	fatemetmhr	Scales (IOI15_scales)	C++17	100 / 100	29 ms	332 KB

scales

//  ~ Be Name Khoda ~  //
 
#include "scales.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
 
using namespace std;
 
typedef long long ll;
 
#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
 
const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;
 
/*
0 -> getLightest()
1 -> getMedian()
2 -> getHeaviest()
getNextLightest();
*/

struct Comp{
    int x[3], cnt[3][3];

    int find_order(int a){
        if(a == x[0])
            return 0;
        if(a == x[1])
            return 1;
        if(a == x[2])
            return 2;
        return -1;
    }

} op1[70];



struct BS{
    int x[3], y[3], cnt[3][3];

    int find_order(int a){
        if(a == x[0])
            return 0;
        if(a == x[1])
            return 1;
        if(a == x[2])
            return 2;
        return -1;
    }

} op2[70];

int pt1 = 0, pt2 = 0;

struct perm{
    int a[6];

    int get_op1(int ty, Comp c){
        int cnt = 0;
        for(int i = 0; i < 6; i++){
            if(c.find_order(a[i]) != -1)
                cnt++;
            if(cnt - 1 == ty)
                return c.find_order(a[i]);
        }
        return -1;
    }

    int get_op2(int ty, BS c){
        for(int i = 0; i < 6; i++) if(a[i] == c.y[ty]){
            for(int j = (i + 1) % 6; ; j = (j + 1) % 6)
                if(c.find_order(a[j]) != -1)
                    return c.find_order(a[j]);
        }
        return -1;
    }    

} av[1000];

bool rem[1000];
 
set <pair<int, pair<int, int>>> bad;


void init(int T) {
    bad.insert({0, {19, 0}});
    bad.insert({0, {10, 2}});
    bad.insert({0, {4, 2}});
    bad.insert({0, {1, 2}});
    int a[6];
    for(int i = 0; i < 6; i++)
        a[i] = i + 1;
    for(int i = 0; i < 720; i++){
        for(int j = 0; j < 6; j++)
            av[i].a[j] = a[j];
        next_permutation(a, a + 6);
    }
    for(int i = 1; i <= 6; i++)
        for(int j = i + 1; j <= 6; j++)
            for(int k = j + 1; k <= 6; k++){
                op1[pt1].x[0] = i;
                op1[pt1].x[1] = j;
                op1[pt1].x[2] = k;
                pt1++;
                op2[pt2].x[0] = i;
                op2[pt2].x[1] = j;
                op2[pt2].x[2] = k;
                int ind = 0;
                for(int x = 1; x <= 6; x++) if(x != i && x != j && x != k)
                    op2[pt2].y[ind++] = x;
                pt2++;
            }
}

 
void orderCoins() {
    int ret[6];

    pair <int, pair<int, int>> last;

    memset(rem, false, sizeof rem);
    int have = 720;
    while(have > 1){
        pair <int, pair<int, int>> mnid = {0, {0, 0}};
        vector <int> mn = {730, 730, 730};
        vector <int> tmp = mn;
        for(int i = 0; i < pt1; i++){
            memset(op1[i].cnt, 0, sizeof op1[i].cnt);
            for(int j = 0; j < 720; j++) if(!rem[j]){
                op1[i].cnt[0][av[j].get_op1(0, op1[i])]++;
                op1[i].cnt[1][av[j].get_op1(1, op1[i])]++;
                op1[i].cnt[2][av[j].get_op1(2, op1[i])]++;
            }
            for(int j = 0; j < 3; j++){
                sort(op1[i].cnt[j], op1[i].cnt[j] + 3);
                tmp[0] = op1[i].cnt[j][2];
                tmp[1] = op1[i].cnt[j][1];
                tmp[2] = op1[i].cnt[j][0];
                if(tmp < mn && bad.find({0, {i, j}}) == bad.end()){
                    mn = tmp;
                    mnid = {0, {i, j}};
                }
            }
        }
        for(int i = 0; i < pt2; i++){
            memset(op2[i].cnt, 0, sizeof op2[i].cnt);
            for(int j = 0; j < 720; j++) if(!rem[j]){
                op2[i].cnt[0][av[j].get_op2(0, op2[i])]++;
                op2[i].cnt[1][av[j].get_op2(1, op2[i])]++;
                op2[i].cnt[2][av[j].get_op2(2, op2[i])]++;
            }
            for(int j = 0; j < 3; j++){
                sort(op2[i].cnt[j], op2[i].cnt[j] + 3);
                tmp[0] = op2[i].cnt[j][2];
                tmp[1] = op2[i].cnt[j][1];
                tmp[2] = op2[i].cnt[j][0];
                if(tmp < mn && bad.find({1, {i, j}}) == bad.end()){
                    mn = tmp;
                    mnid = {1, {i, j}};
                }
            }
        }

        int ans;
        if(mnid.fi == 0){
            int x;
            if(mnid.se.se == 0)
                x = getLightest(op1[mnid.se.fi].x[0], op1[mnid.se.fi].x[1], op1[mnid.se.fi].x[2]);
            if(mnid.se.se == 1)
                x = getMedian(op1[mnid.se.fi].x[0], op1[mnid.se.fi].x[1], op1[mnid.se.fi].x[2]);
            if(mnid.se.se == 2)
                x = getHeaviest(op1[mnid.se.fi].x[0], op1[mnid.se.fi].x[1], op1[mnid.se.fi].x[2]);
            ans = op1[mnid.se.fi].find_order(x);
            for(int i = 0; i < 720; i++) 
                if(!rem[i] && av[i].get_op1(mnid.se.se, op1[mnid.se.fi]) != ans){
                    rem[i] = true;
                    have--;
                }
        }
        else{
            int x = getNextLightest(op2[mnid.se.fi].x[0], op2[mnid.se.fi].x[1], op2[mnid.se.fi].x[2], op2[mnid.se.fi].y[mnid.se.se]);
            ans = op2[mnid.se.fi].find_order(x);
            for(int i = 0; i < 720; i++) 
                if(!rem[i] && av[i].get_op2(mnid.se.se, op2[mnid.se.fi]) != ans){
                    rem[i] = true;
                    have--;
                }
        }
    }
    for(int i = 0; i < 720; i++) if(!rem[i])
        for(int j = 0; j < 6; j++)
            ret[j] = av[i].a[j];
    answer(ret);
    return ;
}

Compilation message

scales.cpp: In function 'void init(int)':
scales.cpp:100:15: warning: unused parameter 'T' [-Wunused-parameter]
  100 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:44:9: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |         if(a == x[2])
      |         ^~
scales.cpp:181:17: note: 'x' was declared here
  181 |             int x;
      |                 ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	212 KB	Output is correct
2	Correct	24 ms	324 KB	Output is correct
3	Correct	24 ms	212 KB	Output is correct
4	Correct	24 ms	324 KB	Output is correct
5	Correct	24 ms	328 KB	Output is correct
6	Correct	28 ms	212 KB	Output is correct
7	Correct	24 ms	212 KB	Output is correct
8	Correct	24 ms	212 KB	Output is correct
9	Correct	25 ms	328 KB	Output is correct
10	Correct	24 ms	212 KB	Output is correct
11	Correct	24 ms	324 KB	Output is correct
12	Correct	26 ms	212 KB	Output is correct
13	Correct	24 ms	212 KB	Output is correct
14	Correct	24 ms	212 KB	Output is correct
15	Correct	24 ms	308 KB	Output is correct
16	Correct	24 ms	328 KB	Output is correct
17	Correct	24 ms	212 KB	Output is correct
18	Correct	24 ms	328 KB	Output is correct
19	Correct	24 ms	212 KB	Output is correct
20	Correct	28 ms	212 KB	Output is correct
21	Correct	24 ms	212 KB	Output is correct
22	Correct	25 ms	212 KB	Output is correct
23	Correct	24 ms	212 KB	Output is correct
24	Correct	25 ms	332 KB	Output is correct
25	Correct	24 ms	212 KB	Output is correct
26	Correct	28 ms	212 KB	Output is correct
27	Correct	24 ms	332 KB	Output is correct
28	Correct	24 ms	328 KB	Output is correct
29	Correct	29 ms	212 KB	Output is correct
30	Correct	24 ms	328 KB	Output is correct
31	Correct	24 ms	308 KB	Output is correct
32	Correct	24 ms	212 KB	Output is correct
33	Correct	24 ms	212 KB	Output is correct
34	Correct	24 ms	212 KB	Output is correct
35	Correct	24 ms	324 KB	Output is correct
36	Correct	24 ms	212 KB	Output is correct
37	Correct	29 ms	324 KB	Output is correct
38	Correct	24 ms	212 KB	Output is correct
39	Correct	26 ms	328 KB	Output is correct
40	Correct	24 ms	328 KB	Output is correct