Submission #778141

#	Time	Username	Problem	Language	Result	Execution time	Memory
778141		Jarif_Rahman	Scales (IOI15_scales)	C++17	45.45 / 100	1 ms	212 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

void init(int T){
}

template<typename it, typename t>
void merge_sort(it l, it r, t && comp){
    int n = r-l;
    if(n <= 1) return;
    int md = n/2;
    merge_sort(l, l+md, comp);
    merge_sort(l+md, r, comp);
    typename remove_reference<decltype(*l)>::type* sth
        = new typename remove_reference<decltype(*l)>::type[n];
    for(int i = 0; i < n; i++) sth[i] = *(l+i);
    merge(sth, sth+md, sth+md, sth+n, l, comp);
    delete[] sth;
}

void orderCoins(){
    int w[6] = {1, 2, 3, 4, 5, 6};

    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    shuffle(w, w+6, rng);

    vector<vector<bool>> c(7, vector<bool>(7, 0)), cc(7, vector<bool>(7, 0));

    merge_sort(w, w+6, [&](int a, int b){
        if(cc[a][b]) return bool(c[a][b]);
        for(int i = 1; i <= 6; i++){
            if(i == a || i == b) continue;
            bool ok = 0, comp;
            if(cc[a][i]){
                ok = 1;
                if(c[a][i]) comp = getLightest(a, b, i) == a;
                else comp = getHeaviest(a, b, i) == b;
            }
            else if(cc[b][i]){
                ok = 1;
                if(c[b][i]) comp = getLightest(a, b, i) == a;
                else comp = getHeaviest(a, b, i) == b;
            }
            if(ok){
                cc[a][b] = 1, cc[b][a] = 1;
                c[a][b] = comp;
                c[b][a] = !comp;
                return comp;
            }
        }

        for(int _i = 0, i = w[_i]; _i <= 6; _i++, i = w[_i]) if(a != i && b != i){
            bool bl = 0;
            for(int j = 1; j <= 6; j++) if(j != i && cc[i][j]) bl = 1;
            if(bl) continue;

            int x = getLightest(a, b, i);
            for(int y: vector<int>{a, b, i}) if(x != y){
                cc[x][y] = 1, cc[y][x] = 1;
                c[x][y] = 1, c[y][x] = 0;
            }
            if(x == a) return true;
            if(x == b) return false;

            x = getMedian(a, b, i);
            cc[a][b] = 1, cc[b][a] = 1;
            if(x == a){
                c[a][b] = 1, c[b][a] = 0;
                return true;
            }
            else{
                c[a][b] = 0, c[b][a] = 1;
                return false;
            }
        }

        for(int _i = 0, i = w[_i]; _i <= 6; _i++, i = w[_i]) if(a != i && b != i){        
            int x = getLightest(a, b, i);
            for(int y: vector<int>{a, b, i}) if(x != y){
                cc[x][y] = 1, cc[y][x] = 1;
                c[x][y] = 1, c[y][x] = 0;
            }
            if(x == a) return true;
            if(x == b) return false;

            x = getMedian(a, b, i);
            cc[a][b] = 1, cc[b][a] = 1;
            if(x == a){
                c[a][b] = 1, c[b][a] = 0;
                return true;
            }
            else{
                c[a][b] = 0, c[b][a] = 1;
                return false;
            }
        }


        return false;
    });

    answer(w);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:10:15: warning: unused parameter 'T' [-Wunused-parameter]
   10 | void init(int T){
      |           ~~~~^
scales.cpp: In instantiation of 'void merge_sort(it, it, t&&) [with it = int*; t = orderCoins()::<lambda(int, int)>]':
scales.cpp:106:6:   required from here
scales.cpp:15:14: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   15 |     int n = r-l;
      |             ~^~
scales.cpp: In instantiation of 'void merge_sort(it, it, t&&) [with it = int*; t = orderCoins()::<lambda(int, int)>&]':
scales.cpp:18:15:   required from 'void merge_sort(it, it, t&&) [with it = int*; t = orderCoins()::<lambda(int, int)>]'
scales.cpp:106:6:   required from here
scales.cpp:15:14: warning: conversion from 'long int' to 'int' may change value [-Wconversion]

• Subtask 1: 45.454545 / 100