Submission #484773

#	Time	Username	Problem	Language	Result	Execution time	Memory
484773		imachug	Scales (IOI15_scales)	C++17	55.56 / 100	1 ms	204 KiB

scales

#include "scales.h"

#include <bits/stdc++.h>

using namespace std;


void init(int T) {
	/* ... */
}


void order3(int a, int b, int c, int* w) {
	w[0] = getLightest(a, b, c);
	w[1] = getMedian(a, b, c);
	w[2] = a + b + c - w[0] - w[1];
}


void order6(int a, int b, int c, int d, int e, int f, int* w) {
	int w1[3];
	int w2[3];
	order3(a, b, c, w1);
	order3(d, e, f, w2);


	vector<int> w_(w1, w1 + 3);

	auto insert_single = [&](int l, int r, int x) {
		if(l == r) {
			w_.insert(w_.begin() + l, x);
		} else if(r - l == 1) {
			// Two variants: single comparison
			bool is_x_less_than_wl = (
				l > 0 ? getHeaviest(w_[0], w_[l], x) == w_[l] :
				getLightest(w_[2], w_[l], x) == x
			);
			if(is_x_less_than_wl) {
				w_.insert(w_.begin() + l, x);
			} else {
				w_.insert(w_.begin() + r, x);
			}
		} else if(r - l == 2) {
			// Two variants
			int median = getMedian(w_[l], x, w_[l + 1]);
			if(median == w_[l]) {
				w_.insert(w_.begin() + l, x);
			} else if(median == x) {
				w_.insert(w_.begin() + l + 1, x);
			} else {
				w_.insert(w_.begin() + r, x);
			}
		} else if(r - l == 3) {
			int y = getNextLightest(w_[l], w_[l + 1], w_[l + 2], x);
			if(y != w_[l]) {
				// Insert just before y
				w_.insert(find(w_.begin(), w_.end(), y), x);
			} else {
				// Either less than everything or greater than everything
				bool is_x_less_than_wl = (
					l > 0 ? getHeaviest(w_[0], w_[l], x) == w_[l] :
					getLightest(w_[2], w_[l], x) == x
				);
				if(is_x_less_than_wl) {
					// Insert just before the first one
					w_.insert(w_.begin() + l, x);
				} else {
					// insert to the end
					w_.insert(w_.begin() + r, x);
				}
			}
		} else {
			assert(false);
		}
	};


	// Insert w2[1]
	int y = getNextLightest(a, b, c, w2[1]);
	if(y != w1[0]) {
		// Exact known point
		int idx = find(w1, w1 + 3, y) - w1;
		w_.insert(w_.begin() + idx, w2[1]);
		// Insert w2[0] and w2[2]
		insert_single(idx + 1, 4, w2[2]);
		insert_single(0, idx, w2[0]);
	} else {
		// Either less than everything or greater than everything
		bool is_w2_1_less_than_w1_0 = getLightest(w1[0], w1[1], w2[1]) == w2[1];
		if(is_w2_1_less_than_w1_0) {
			// Less than everything
			insert_single(0, 3, w2[2]);
			w_.insert(w_.begin(), w2[1]);
			w_.insert(w_.begin(), w2[0]);
		} else {
			// Greater than everything
			insert_single(0, 3, w2[0]);
			w_.push_back(w2[1]);
			w_.push_back(w2[2]);
		}
	}


	copy(w_.begin(), w_.end(), w);
}


void orderCoins() {
	int W[6];
	order6(1, 2, 3, 4, 5, 6, W);
	answer(W);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:8:15: warning: unused parameter 'T' [-Wunused-parameter]
    8 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void order6(int, int, int, int, int, int, int*)':
scales.cpp:82:33: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   82 |   int idx = find(w1, w1 + 3, y) - w1;
      |             ~~~~~~~~~~~~~~~~~~~~^~~~

• Subtask 1: 55.555556 / 100