Submission #579119

#	Time	Username	Problem	Language	Result	Execution time	Memory
579119		CSQ31	Scales (IOI15_scales)	C++17	0 / 100	787 ms	524288 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)

scales.cpp: In constructor 'query::query(int, int, int, int, int)':
scales.cpp:8:40: warning: declaration of 'd' shadows a member of 'query' [-Wshadow]
    8 |  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
    9 |  int t, a, b, c, d;
      |                  ^
scales.cpp:8:33: warning: declaration of 'c' shadows a member of 'query' [-Wshadow]
    8 |  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
    9 |  int t, a, b, c, d;
      |               ^
scales.cpp:8:26: warning: declaration of 'b' shadows a member of 'query' [-Wshadow]
    8 |  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
    9 |  int t, a, b, c, d;
      |            ^
scales.cpp:8:19: warning: declaration of 'a' shadows a member of 'query' [-Wshadow]
    8 |  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
    9 |  int t, a, b, c, d;
      |         ^
scales.cpp:8:12: warning: declaration of 't' shadows a member of 'query' [-Wshadow]
    8 |  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
    9 |  int t, a, b, c, d;
      |      ^
scales.cpp: In constructor 'query::query(int, int, int, int, int)':
scales.cpp:8:40: warning: declaration of 'd' shadows a member of 'query' [-Wshadow]
    8 |  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
    9 |  int t, a, b, c, d;
      |                  ^
scales.cpp:8:33: warning: declaration of 'c' shadows a member of 'query' [-Wshadow]
    8 |  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
    9 |  int t, a, b, c, d;
      |               ^
scales.cpp:8:26: warning: declaration of 'b' shadows a member of 'query' [-Wshadow]
    8 |  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
    9 |  int t, a, b, c, d;
      |            ^
scales.cpp:8:19: warning: declaration of 'a' shadows a member of 'query' [-Wshadow]
    8 |  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
    9 |  int t, a, b, c, d;
      |         ^
scales.cpp:8:12: warning: declaration of 't' shadows a member of 'query' [-Wshadow]
    8 |  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
    9 |  int t, a, b, c, d;
      |      ^
scales.cpp: In constructor 'query::query(int, int, int, int, int)':
scales.cpp:8:40: warning: declaration of 'd' shadows a member of 'query' [-Wshadow]
    8 |  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
    9 |  int t, a, b, c, d;
      |                  ^
scales.cpp:8:33: warning: declaration of 'c' shadows a member of 'query' [-Wshadow]
    8 |  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
    9 |  int t, a, b, c, d;
      |               ^
scales.cpp:8:26: warning: declaration of 'b' shadows a member of 'query' [-Wshadow]
    8 |  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
    9 |  int t, a, b, c, d;
      |            ^
scales.cpp:8:19: warning: declaration of 'a' shadows a member of 'query' [-Wshadow]
    8 |  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
    9 |  int t, a, b, c, d;
      |         ^
scales.cpp:8:12: warning: declaration of 't' shadows a member of 'query' [-Wshadow]
    8 |  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
    9 |  int t, a, b, c, d;
      |      ^
scales.cpp: In function 'bool make_tree(node*, std::set<int>)':
scales.cpp:59:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  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]
   70 | 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]
   45 |  }
      |  ^
scales.cpp: In function 'void orderCoins()':
scales.cpp:43:3: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   43 |   if (res == b) return 1;
      |   ^~
scales.cpp:37:7: note: 'res' was declared here
   37 |   int res;
      |       ^~~

• Subtask 1: 0 / 100