| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 797375 | thimote75 | Scales (IOI15_scales) | C++14 | 24 ms | 636 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
using idata = vector<int>;
using igrid = vector<idata>;
const int STATE_SIZE = 6;
igrid all_states;
struct Status {
idata states_possible;
void show () {
for (int pos : states_possible) {
cout << "[ ";
for (int u : all_states[pos]) cout << u << " ";
cout << "] ";
}
cout << endl;
}
};
struct Move {
bool is_valid = false;
bool is_answer = false;
int answer_id = -1;
int type;
int A, B, C, D;
Move* resA = nullptr;
Move* resB = nullptr;
Move* resC = nullptr;
Move (bool valid) {
is_valid = valid;
}
Move (bool valid, bool answer) {
is_valid = valid;
is_answer = answer;
}
Move (int result) {
is_valid = true;
is_answer = true;
answer_id = result;
}
void show_spaces (int depth) {
for (int u = 0; u < depth; u ++) cout << " ";
}
void show (int depth = 0) {
if (is_answer) {
if (answer_id == -1) {
cout << endl;
return ;
}
show_spaces(depth);
for (int u : all_states[answer_id]) cout << u << " "; cout << endl;
return ;
}
show_spaces(depth);
cout << type << ": " << A << " " << B << " " << C;
if (type == 4) cout << " " << D;
cout << endl;
if (resA != nullptr) resA->show(depth + 1);
if (resB != nullptr) resB->show(depth + 1);
if (resC != nullptr) resC->show(depth + 1);
}
Move* traverse () {
if (is_answer) return this;
int result;
if (type == 0) result = getHeaviest(A, B, C);
if (type == 1) result = getMedian (A, B, C);
if (type == 2) result = getLightest(A, B, C);
if (type == 4) result = getNextLightest(A, B, C, D);
if (result == A) return resA;
if (result == B) return resB;
if (result == C) return resC;
return this;
}
};
Status filter_gamma (Status &state, int a, int b, int c, int result, int gamma) {
Status answer;
for (int answer_id : state.states_possible) {
int res = 0;
for (int u : all_states[answer_id]) {
if (u == a || u == b || u == c) res ++;
if (u == result) break ;
}
if (res != gamma) continue ;
answer.states_possible.push_back(answer_id);
}
return answer;
}
Status filter (Status &state, int type, int a, int b, int c, int result) {
if (type == 0) return filter_gamma(state, a, b, c, result, 3);
if (type == 1) return filter_gamma(state, a, b, c, result, 2);
if (type == 2) return filter_gamma(state, a, b, c, result, 1);
return state;
}
Status filter4 (Status &state, int a, int b, int c, int d, int result) {
Status answer;
for (int answer_id : state.states_possible) {
int first = -1; int res = 0;
for (int u : all_states[answer_id]) {
if (a == u || b == u || c == u) {
res ++;
if (res == 3) break ;
if (first == -1) first = u;
}
if (u == d) {
first = -1;
}
}
if (first != result) continue ;
answer.states_possible.push_back(answer_id);
}
return answer;
}
Move* traverse (Status &state, int rem) {
if (state.states_possible.size() == 0)
return new Move(true, true);
if (state.states_possible.size() == 1)
return new Move(state.states_possible[0]);
int nextRem = rem / 3;
for (int type = 0; type < 3; type ++) {
for (int a = 1; a <= STATE_SIZE; a ++) {
for (int b = 1; b <= STATE_SIZE; b ++) {
if (a == b) continue ;
for (int c = 1; c <= STATE_SIZE; c ++) {
if (a == c || b == c) continue ;
Status sA = filter(state, type, a, b, c, a);
if (sA.states_possible.size() > nextRem) continue ;
Status sB = filter(state, type, a, b, c, b);
if (sB.states_possible.size() > nextRem) continue ;
Status sC = filter(state, type, a, b, c, c);
if (sC.states_possible.size() > nextRem) continue ;
Move* mA = traverse(sA, nextRem);
if (!mA->is_valid) continue ;
Move* mB = traverse(sB, nextRem);
if (!mB->is_valid) continue ;
Move* mC = traverse(sC, nextRem);
if (!mC->is_valid) continue ;
//cout << rem << ": " << type << " " << a << " " << b << " " << c << "\n";
Move* result = new Move(true);
result->A = a; result->B = b; result->C = c;
result->resA = mA;
result->resB = mB;
result->resC = mC;
result->type = type;
return result;
}
}
}
}
for (int a = 1; a <= STATE_SIZE; a ++) {
for (int b = 1; b <= STATE_SIZE; b ++) {
if (a == b) continue ;
for (int c = 1; c <= STATE_SIZE; c ++) {
if (a == c || b == c) continue ;
for (int d = 1; d <= STATE_SIZE; d ++) {
if (a == d || b == d || c == d) continue ;
Status sA = filter4(state, a, b, c, d, a);
if (sA.states_possible.size() > nextRem) continue ;
Status sB = filter4(state, a, b, c, d, b);
if (sB.states_possible.size() > nextRem) continue ;
Status sC = filter4(state, a, b, c, d, c);
if (sC.states_possible.size() > nextRem) continue ;
Move* mA = traverse(sA, nextRem);
if (!mA->is_valid) continue ;
Move* mB = traverse(sB, nextRem);
if (!mB->is_valid) continue ;
Move* mC = traverse(sC, nextRem);
if (!mC->is_valid) continue ;
Move* result = new Move(true);
result->type = 4;
result->A = a;
result->B = b;
result->C = c;
result->D = d;
result->resA = mA;
result->resB = mB;
result->resC = mC;
//cout << rem << ": " << 4 << " " << a << " " << b << " " << c << "\n";
return result;
}
}
}
}
return new Move(false);
}
void init_states (vector<int> &values) {
if (values.size() == STATE_SIZE) {
all_states.push_back(values);
return ;
}
for (int i = 1; i <= STATE_SIZE; i ++) {
bool unique = true;
for (int u : values) if (i == u) unique = false;
if (!unique) continue ;
values.push_back(i);
init_states(values);
values.pop_back();
}
}
Move* answerMove;
void init(int T) {
vector<int> state; init_states(state);
Status initial_state;
for (int i = 0; i < all_states.size(); i ++) initial_state.states_possible.push_back(i);
answerMove = traverse(initial_state, 729);
assert(answerMove->is_valid);
}
void orderCoins() {
Move* localMove = answerMove;
for (int i = 0; i < 6; i ++)
localMove = localMove->traverse();
int ans[STATE_SIZE];
for (int i = 0; i < STATE_SIZE; i ++)
ans[i] = all_states[localMove->answer_id][i];
answer(ans);
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||