| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 797404 |
2023-07-29T10:29:50 Z |
thimote75 |
Scales (IOI15_scales) |
C++14 |
|
101 ms |
516 KB |
#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 (first == -1) first = u;
if (res == 3) break ;
}
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);
}
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
scales.cpp: In member function 'void Move::show(int)':
scales.cpp:61:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
61 | for (int u : all_states[answer_id]) cout << u << " "; cout << endl;
| ^~~
scales.cpp:61:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
61 | for (int u : all_states[answer_id]) cout << u << " "; cout << endl;
| ^~~~
scales.cpp: In function 'Move* traverse(Status&, int)':
scales.cpp:151:51: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
151 | if (sA.states_possible.size() > nextRem) continue ;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
scales.cpp:153:51: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
153 | if (sB.states_possible.size() > nextRem) continue ;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
scales.cpp:155:51: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
155 | if (sC.states_possible.size() > nextRem) continue ;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
scales.cpp:189:51: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
189 | if (sA.states_possible.size() > nextRem) continue ;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
scales.cpp:191:51: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
191 | if (sB.states_possible.size() > nextRem) continue ;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
scales.cpp:193:51: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
193 | if (sC.states_possible.size() > nextRem) continue ;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:247:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
247 | for (int i = 0; i < all_states.size(); i ++) initial_state.states_possible.push_back(i);
| ~~^~~~~~~~~~~~~~~~~~~
scales.cpp:243:15: warning: unused parameter 'T' [-Wunused-parameter]
243 | void init(int T) {
| ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:84:9: warning: 'result' may be used uninitialized in this function [-Wmaybe-uninitialized]
84 | if (result == B) return resB;
| ^~
scales.cpp:77:13: note: 'result' was declared here
77 | int result;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
82 ms |
392 KB |
Output is correct |
| 2 |
Correct |
90 ms |
400 KB |
Output is correct |
| 3 |
Correct |
79 ms |
372 KB |
Output is correct |
| 4 |
Correct |
79 ms |
340 KB |
Output is correct |
| 5 |
Correct |
85 ms |
364 KB |
Output is correct |
| 6 |
Correct |
89 ms |
360 KB |
Output is correct |
| 7 |
Correct |
80 ms |
348 KB |
Output is correct |
| 8 |
Correct |
92 ms |
420 KB |
Output is correct |
| 9 |
Correct |
79 ms |
368 KB |
Output is correct |
| 10 |
Correct |
83 ms |
384 KB |
Output is correct |
| 11 |
Correct |
80 ms |
368 KB |
Output is correct |
| 12 |
Correct |
99 ms |
400 KB |
Output is correct |
| 13 |
Correct |
81 ms |
352 KB |
Output is correct |
| 14 |
Correct |
80 ms |
376 KB |
Output is correct |
| 15 |
Correct |
87 ms |
364 KB |
Output is correct |
| 16 |
Correct |
81 ms |
364 KB |
Output is correct |
| 17 |
Correct |
81 ms |
372 KB |
Output is correct |
| 18 |
Correct |
87 ms |
516 KB |
Output is correct |
| 19 |
Correct |
82 ms |
368 KB |
Output is correct |
| 20 |
Correct |
79 ms |
372 KB |
Output is correct |
| 21 |
Correct |
88 ms |
364 KB |
Output is correct |
| 22 |
Correct |
86 ms |
352 KB |
Output is correct |
| 23 |
Correct |
94 ms |
372 KB |
Output is correct |
| 24 |
Correct |
79 ms |
360 KB |
Output is correct |
| 25 |
Correct |
79 ms |
340 KB |
Output is correct |
| 26 |
Correct |
82 ms |
364 KB |
Output is correct |
| 27 |
Correct |
80 ms |
400 KB |
Output is correct |
| 28 |
Correct |
97 ms |
412 KB |
Output is correct |
| 29 |
Correct |
80 ms |
348 KB |
Output is correct |
| 30 |
Correct |
85 ms |
396 KB |
Output is correct |
| 31 |
Correct |
82 ms |
400 KB |
Output is correct |
| 32 |
Correct |
82 ms |
376 KB |
Output is correct |
| 33 |
Correct |
101 ms |
400 KB |
Output is correct |
| 34 |
Correct |
85 ms |
364 KB |
Output is correct |
| 35 |
Correct |
81 ms |
360 KB |
Output is correct |
| 36 |
Correct |
79 ms |
368 KB |
Output is correct |
| 37 |
Correct |
81 ms |
400 KB |
Output is correct |
| 38 |
Correct |
85 ms |
400 KB |
Output is correct |
| 39 |
Correct |
87 ms |
420 KB |
Output is correct |
| 40 |
Correct |
80 ms |
376 KB |
Output is correct |
