Submission #786798

#	Time	Username	Problem	Language	Result	Execution time	Memory
786798		esomer	Scales (IOI15_scales)	C++17	71.43 / 100	1 ms	340 KiB

scales

#include<bits/stdc++.h>
#include "scales.h"

using namespace std;

typedef long long ll;

int ans[6];

void init(int T){}

void eras(vector<int>& left, int val){
	vector<int> nw;
	for(int x : left){
		if(x == val) continue;
		nw.push_back(x);
	}
	left = nw;
}

void reconstruct(vector<int>& W, int ind, int val){
	if(ind == (int)W.size()){
		W.push_back(val);
		return;
	}
	vector<int> nw;
	for(int i = 0; i < (int)W.size(); i++){
		if(i == ind) nw.push_back(val);
		nw.push_back(W[i]);
	}
	W = nw;
}

void orderCoins(){
	vector<int> left = {1, 2, 3};
	vector<int> W(3);
	int curr = 0;
	while((int)left.size() > 2){
		int a = getLightest(left[0], left[1], left[2]);
		if((int)left.size() == 3){
			W[curr] = a;
			curr++;
			eras(left, a);
			continue;
		}
	}
	int a = getHeaviest(4, left[0], left[1]); //If it is 4, I have guessed four in one query, which is awesome. If it isn't four, proceed as normal.
	if(left[0] == a){
		W[curr] = left[1];
		W[curr+1] = left[0];
	}else if(left[1] == a){
		W[curr] = left[0];
		W[curr+1] = left[1];
	}else{
		W.push_back(4);
		a = getHeaviest(W[0], left[0], left[1]);
		if(left[0] == a){
			W[curr] = left[1];
			W[curr+1] = left[0];
		}else{
			W[curr] = left[0];
			W[curr+1] = left[1];
		}
	}
	//Now, I know that 4 is smaller than W[2]. Or I already know 4. If it is smaller, I can ask for FindNextHighest and I know it will give me an accurate answer.
	//Now I want to add 4 and 5 in 3 queries.
	if((int)W.size() == 3){
		a = getNextLightest(W[0], W[1], W[2], 4);
		int ind;
		if(a == W[0]) ind = 0;
		else if(a == W[1]) ind = 1;
		else if(a == W[2]) ind = 2;
		reconstruct(W, ind, 4);
	}
	
	//Now I should decide where the fifth one is.
	
	a = getNextLightest(W[0], W[2], W[3], 5);
	int ind = 3;
	if(a == W[2]) ind = 2;
	if(a == W[0]){
		int b = getLightest(5, W[0], W[1]);
		if(b == 5) ind = 0;
		else ind = 4;
	}else{
		int b = getNextLightest(W[1], W[2], W[3], 5);
		if(b == W[3]) ind = min(ind, 3);
		if(b == W[2]) ind = min(ind, 2);
		if(b == W[1]) ind = min(ind, 1);
	}
	reconstruct(W, ind, 5);
	
	//Now I should decide where the sixth one is.
	a = getNextLightest(W[0], W[3], W[4], 6);
	ind = 4;
	if(a == W[3]) ind = 3;
	if(a == W[0]){
		int b = getLightest(6, W[0], W[1]);
		if(b == 6) ind = 0;
		else ind = 5;
	}else{
		int b = getNextLightest(W[1], W[2], W[4], 6);
		if(b == W[4]) ind = min(ind, 4);
		if(b == W[2]) ind = min(ind, 2);
		if(b == W[1]) ind = min(ind, 1);
	}
	reconstruct(W, ind, 6);
	for(int i = 0; i < 6; i++) ans[i] = W[i];
	answer(ans);
	return;
}

//~ #define MAXN 6
//~ #define MAX_ANSWER_CALLS 1

//~ static int realC[MAXN];
//~ static int ind[MAXN];
//~ static int numQueries;
//~ static int numAnswerCalls;

//~ static int arra[300];
//~ static int arraySize;
//~ static int ptr;

//~ static void readAll() {
  //~ ptr = 0;
  //~ arraySize = 0;
  //~ int x;
  //~ while (scanf("%d", &x) == 1) {
    //~ arra[arraySize++] = x;
    //~ assert(arraySize <= 300);
  //~ }
//~ }

//~ static int readInt() {
  //~ assert(ptr < arraySize);
  //~ int res = arra[ptr++];
  //~ return res;
//~ }

//~ static void initNewTest() {
  //~ for (int i = 0; i < MAXN; i++) {
    //~ realC[i] = readInt();
    //~ realC[i]--;
    //~ ind[realC[i]] = i;
  //~ }

  //~ numQueries = 0;
  //~ numAnswerCalls = 0;
//~ }

//~ void answer(int C[]) {
  //~ int i;

  //~ numAnswerCalls++;
  //~ if (numAnswerCalls > MAX_ANSWER_CALLS)
    //~ return;

  //~ for (i = 0; i < 6; i++)
    //~ printf("%d ", C[i]);
  //~ printf("%d\n", numQueries);
//~ }

//~ static void checkQuery(int A, int B, int C, int D) {
  //~ if (D == -1) {
    //~ if (A < 1 || A > 6 || B < 1 || B > 6 || C < 1 || C > 6)
      //~ assert(0);
    //~ if (A == B || B == C || A == C)
      //~ assert(0);
  //~ } else {
    //~ if (A < 1 || A > 6 || B < 1 || B > 6 || C < 1 || C > 6 || D < 1 || D > 6)
      //~ assert(0);
    //~ if (A == B || A == C || A == D || B == C || B == D || C == D)
      //~ assert(0);
  //~ }
//~ }

//~ int getMedian(int A, int B, int C) {
  //~ numQueries++;
  //~ checkQuery(A, B, C, -1);

  //~ A--;
  //~ B--;
  //~ C--;

  //~ if (ind[B] < ind[A] && ind[A] < ind[C])
    //~ return A + 1;

  //~ if (ind[C] < ind[A] && ind[A] < ind[B])
    //~ return A + 1;

  //~ if (ind[A] < ind[B] && ind[B] < ind[C])
    //~ return B + 1;

  //~ if (ind[C] < ind[B] && ind[B] < ind[A])
    //~ return B + 1;

  //~ return C + 1;
//~ }

//~ int getHeaviest(int A, int B, int C) {
  //~ numQueries++;
  //~ checkQuery(A, B, C, -1);

  //~ A--;
  //~ B--;
  //~ C--;

  //~ if (ind[A] > ind[B] && ind[A] > ind[C])
    //~ return A + 1;

  //~ if (ind[B] > ind[A] && ind[B] > ind[C])
    //~ return B + 1;

  //~ return C + 1;
//~ }

//~ int getLightest(int A, int B, int C) {
  //~ numQueries++;
  //~ checkQuery(A, B, C, -1);

  //~ A--;
  //~ B--;
  //~ C--;

  //~ if (ind[A] < ind[B] && ind[A] < ind[C])
    //~ return A + 1;

  //~ if (ind[B] < ind[A] && ind[B] < ind[C])
    //~ return B + 1;

  //~ return C + 1;
//~ }

//~ int getNextLightest(int A, int B, int C, int D) {
  //~ int allLess = 1;

  //~ numQueries++;
  //~ checkQuery(A, B, C, D);

  //~ A--;
  //~ B--;
  //~ C--;
  //~ D--;

  //~ if (ind[A] > ind[D] || ind[B] > ind[D] || ind[C] > ind[D])
    //~ allLess = 0;

  //~ if (allLess == 1) {
    //~ if (ind[A] < ind[B] && ind[A] < ind[C])
      //~ return A + 1;

    //~ if (ind[B] < ind[A] && ind[B] < ind[C])
      //~ return B + 1;

    //~ return C + 1;
  //~ }

  //~ if (ind[A] > ind[D]) {
    //~ if ((ind[A] < ind[B] || ind[B] < ind[D]) &&
        //~ (ind[A] < ind[C] || ind[C] < ind[D]))
      //~ return A + 1;
  //~ }

  //~ if (ind[B] > ind[D]) {
    //~ if ((ind[B] < ind[A] || ind[A] < ind[D]) &&
        //~ (ind[B] < ind[C] || ind[C] < ind[D]))
      //~ return B + 1;
  //~ }

  //~ return C + 1;
//~ }

//~ int main() {
	
	//~ freopen("in.txt", "r", stdin);

  //~ readAll();
  //~ fclose(stdin);
  //~ int T, i;

  //~ T = readInt();

  //~ init(T);

  //~ for (i = 1; i <= T; i++) {
    //~ initNewTest();
    //~ orderCoins();
  //~ }

  //~ return 0;
//}

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 function 'void orderCoins()':
scales.cpp:73:14: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |   reconstruct(W, ind, 4);
      |   ~~~~~~~~~~~^~~~~~~~~~~

• Subtask 1: 71.428571 / 100