Submission #484772

#	Time	Username	Problem	Language	Result	Execution time	Memory
484772		imachug	Scales (IOI15_scales)	C++17	45.57 / 100	1 ms	284 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);


	int max = getHeaviest(w1[0], w1[2], w2[2]);
	auto lt = [&](int i, int j) {
		if(i == max) {
			return false;
		} else if(j == max) {
			return true;
		}
		return getLightest(i, j, max) == i;
	};


	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
			if(lt(x, w_[l])) {
				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
				if(lt(x, w_[l])) {
					// 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
		if(lt(w2[1], 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);


	// int max = getHeaviest(w1[0], w1[2], w2[2]);

	// auto lt = [&](int i, int j) {
	// 	if(i == max) {
	// 		return false;
	// 	} else if(j == max) {
	// 		return true;
	// 	}
	// 	return getLightest(i, j, max) == i;
	// };

	// int i = 0;
	// int j = 0;
	// while(i < 3 || j < 3) {
	// 	if(i == 3) {
	// 		w[i + j] = w2[j];
	// 		j++;
	// 	} else if(j == 3) {
	// 		w[i + j] = w1[i];
	// 		i++;
	// 	} else {
	// 		if(lt(w1[i], w2[j])) {
	// 			w[i + j] = w1[i];
	// 			i++;
	// 		} else {
	// 			w[i + j] = w2[j];
	// 			j++;
	// 		}
	// 	}
	// }
}


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:85:33: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   85 |   int idx = find(w1, w1 + 3, y) - w1;
      |             ~~~~~~~~~~~~~~~~~~~~^~~~

• Subtask 1: 45.568182 / 100