제출 #797372

#제출 시각아이디문제언어결과실행 시간메모리
797372thimote75저울 (IOI15_scales)C++14
0 / 100
24 ms648 KiB
#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); } 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); }

컴파일 시 표준 에러 (stderr) 메시지

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 timeMemoryGrader output
Fetching results...