Submission #45773

#	Time	Username	Problem	Language	Result	Execution time	Memory
45773		jun6873	Scales (IOI15_scales)	C++11	100 / 100	109 ms	1512 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
using namespace std;

int p[720][7] = {{0, 1, 2, 3, 4, 5, 6}};
struct query {
	query() {}
	query(int t, int a, int b, int c, int d) : t(t), a(a), b(b), c(c), d(d) {}
	int t, a, b, c, d;
	int moi(int k) {
		if (t==1) { // Heaviest
			if (p[k][a] > p[k][b] and p[k][a] > p[k][c]) return 0;
			else return (p[k][b] > p[k][c]) ? 1 : 2;
		} if (t==2) { // Lightest
			if (p[k][a] < p[k][b] and p[k][a] < p[k][c]) return 0;
			else return (p[k][b] < p[k][c]) ? 1 : 2;
		} if (t==3) { // Median
			if (p[k][a] < p[k][b]) {
				if (p[k][b] < p[k][c]) return 1;
				else return p[k][a] < p[k][c] ? 2 : 0;
			} else {
				if (p[k][a] < p[k][c]) return 0;
				else return p[k][b] < p[k][c] ? 2 : 1;
			}
		} if (t==4) { // NextHeaviest
			int x = p[k][a], y = p[k][b], z = p[k][c];
			if (not (x < p[k][d] and y < p[k][d] and z < p[k][d])) {
				if (x < p[k][d]) x = 7;
				if (y < p[k][d]) y = 7;
				if (z < p[k][d]) z = 7;
			}
			if (x<y and x<z) return 0;
			else return y<z ? 1 : 2;
		} return -1;
	}
	int real() {
		int res;
		if (t==1) res = getHeaviest(a, b, c);
		if (t==2) res = getLightest(a, b, c);
		if (t==3) res = getMedian(a, b, c);
		if (t==4) res = getNextLightest(a, b, c, d);
		if (res == a) return 0;
		if (res == b) return 1;
		if (res == c) return 2;
	}
};
vector<query> q;

struct node {
	query q;
	node *ch[3];
	set<int> s;
} *root;

bool make_tree(node* k, set<int> s) {
	k->s = s;
	for (int i=0; i<3; i++) if (!k->ch[i]) k->ch[i] = new node();
	if (s.size() <= 1) return true;
	for (int i=0; i<q.size(); i++) {
		set<int> r[3];
		for (int e : s) r[q[i].moi(e)].insert(e);
		if (max({r[0].size(), r[1].size(), r[2].size()}) - min({r[0].size(), r[1].size(), r[2].size()}) < 2)
			if (make_tree(k->ch[0], r[0]) and make_tree(k->ch[1], r[1]) and make_tree(k->ch[2], r[2])) {
				k->q = q[i];
				return true;
			}
	} return false;
}

void init(int T) {
	for (int x=1; x<=6; x++) for (int y=x+1; y<=6; y++) for (int z=y+1; z<=6; z++) {
		q.emplace_back(1, x, y, z, -1);
		q.emplace_back(2, x, y, z, -1);
		q.emplace_back(3, x, y, z, -1);
		for (int w=1; w<=6; w++) if (x!=w and y!=w and z!=w) q.emplace_back(4, x, y, z, w);
	}

    for (int i=1; i<720; i++) {
		copy(p[i-1]+1, p[i-1]+7, p[i]+1);
		next_permutation(p[i]+1, p[i]+7);
    }

    set<int> st;
    for (int i=0; i<720; i++) st.insert(i);
    root = new node();
	make_tree(root, st);
}

void orderCoins() {
	node *now = root;
    while (now->s.size() > 1) {
		now = now->ch[now->q.real()];
    }
    int ans[6], *rans = p[*now->s.begin()];
    for (int i=1; i<=6; i++) ans[rans[i]-1] = i;
    answer(ans);
}

Compilation message (stderr)

In file included from grader.c:2:0:
graderlib.c: In function 'void answer(int*)':
graderlib.c:53:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (_ghksjhdfkae19ga_ > 1) 
     ^~
graderlib.c:56:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  for (i = 0; i < 6; i++) {
  ^~~
scales.cpp: In constructor 'query::query(int, int, int, int, int)':
scales.cpp:8:43: warning: declaration of 'd' shadows a member of 'query' [-Wshadow]
  query(int t, int a, int b, int c, int d) : t(t), a(a), b(b), c(c), d(d) {}
                                           ^
scales.cpp:9:18: note: shadowed declaration is here
  int t, a, b, c, d;
                  ^
scales.cpp:8:43: warning: declaration of 'c' shadows a member of 'query' [-Wshadow]
  query(int t, int a, int b, int c, int d) : t(t), a(a), b(b), c(c), d(d) {}
                                           ^
scales.cpp:9:15: note: shadowed declaration is here
  int t, a, b, c, d;
               ^
scales.cpp:8:43: warning: declaration of 'b' shadows a member of 'query' [-Wshadow]
  query(int t, int a, int b, int c, int d) : t(t), a(a), b(b), c(c), d(d) {}
                                           ^
scales.cpp:9:12: note: shadowed declaration is here
  int t, a, b, c, d;
            ^
scales.cpp:8:43: warning: declaration of 'a' shadows a member of 'query' [-Wshadow]
  query(int t, int a, int b, int c, int d) : t(t), a(a), b(b), c(c), d(d) {}
                                           ^
scales.cpp:9:9: note: shadowed declaration is here
  int t, a, b, c, d;
         ^
scales.cpp:8:43: warning: declaration of 't' shadows a member of 'query' [-Wshadow]
  query(int t, int a, int b, int c, int d) : t(t), a(a), b(b), c(c), d(d) {}
                                           ^
scales.cpp:9:6: note: shadowed declaration is here
  int t, a, b, c, d;
      ^
scales.cpp: In function 'bool make_tree(node*, std::set<int>)':
scales.cpp:59:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<q.size(); i++) {
                ~^~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:70:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T) {
               ^
scales.cpp: In member function 'int query::real()':
scales.cpp:45:2: warning: control reaches end of non-void function [-Wreturn-type]
  }
  ^
scales.cpp: In function 'void orderCoins()':
scales.cpp:44:3: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if (res == c) return 2;
   ^~
scales.cpp:37:7: note: 'res' was declared here
   int res;
       ^~~

• Subtask 1: 100 / 100