제출 #1029375

#제출 시각아이디문제언어결과실행 시간메모리
1029375boris_mihov로봇 대회 (IOI23_robot)C++17
28 / 100
120 ms6776 KiB
#include "robot.h" #include <algorithm> #include <iostream> #include <numeric> #include <cassert> #include <vector> #include <set> typedef long long llong; const int MAXN = 20; const int Z_MAX = 9; struct State { bool isDone; bool isClearing; bool haventPassed; bool traversedThrough; bool isOutside; bool isOnStick; bool isCross; int dep; State() { isDone = traversedThrough = haventPassed = dep = isOutside = isCross = isOnStick = isClearing = 0; } int getNUM() { if (isDone) return 1; if (isOutside) return -2; if (isCross) return -1; if (haventPassed) return 0; if (isOnStick) return 8; if (isClearing) return 9; return 3 * (int)(traversedThrough) + dep + 2; // zMAX == 9 } void setState(int num) { isDone = traversedThrough = haventPassed = dep = isOutside = isCross = isOnStick = isClearing = 0; if (num == -2) { isOutside = 1; return; } if (num == -1) { isCross = 1; return; } if (num == 0) { haventPassed = 1; return; } if (num == 1) { isDone = 1; return; } if (num == 8) { isOnStick = 1; return; } if (num == 9) { isClearing = 1; return; } assert(num <= 7); if (num > 4) { traversedThrough = 1; dep = num - 5; return; } dep = num - 2; } }; State state[5]; std::vector <int> nums; bool isNeighboor[5]; char getDirection[4] = {'W', 'S', 'E', 'N'}; char getOpposite[4] = {'E', 'N', 'W', 'S'}; void rec(int idx) { if (idx == 5) { if (state[0].isCross || state[0].isOutside) { return; } if (2 <= state[0].getNUM() && state[0].getNUM() <= 7) { for (int i = 1 ; i <= 4 ; ++i) { if (state[i].isDone || state[i].isClearing) { set_instruction(nums, 9, 'H'); return; } } } if (state[0].isClearing) { for (int i = 1 ; i <= 4 ; ++i) { if (2 <= state[i].getNUM() && state[i].getNUM() <= 7) { set_instruction(nums, 9, getDirection[i - 1]); return; } } for (int i = 4 ; i >= 1 ; --i) { if (state[i].getNUM() == 9) { set_instruction(nums, 0, getDirection[i - 1]); return; } } for (int i = 1 ; i <= 4 ; ++i) { if (state[i].getNUM() == 1) { set_instruction(nums, 0, getDirection[i - 1]); return; } } return; } if (state[0].isDone) { for (int i = 1 ; i <= 4 ; ++i) { if (2 <= state[i].getNUM() && state[i].getNUM() <= 7) { set_instruction(nums, 1, getDirection[i - 1]); return; } } for (int i = 1 ; i <= 4 ; ++i) { if (state[i].getNUM() == 8) { set_instruction(nums, 1, getDirection[i - 1]); return; } } return; } int neighOnStick = 0; for (int i = 1 ; i <= 4 ; ++i) { if (state[i].isOnStick || state[i].isDone) { neighOnStick++; } } if (neighOnStick) { if (neighOnStick > 2) { return; } if (state[2].isOutside && state[3].isOutside) { set_instruction(nums, 1, 'T'); return; } if (neighOnStick == 1) { char parent = 'H'; for (int i = 1 ; i <= 4 ; ++i) { if (state[i].isCross || state[i].isOutside || state[i].traversedThrough || state[i].haventPassed || state[i].isOnStick) { continue; } if (state[i].dep != (state[0].dep + 1) % 3) { parent = getDirection[i - 1]; break; } } if (parent == 'H' && !(state[1].isOutside && state[4].isOutside)) { return; } if (parent != 'H') { State newState = state[0]; newState.isOnStick = 1; set_instruction(nums, newState.getNUM(), parent); return; } State newState = state[0]; newState.isDone = 1; set_instruction(nums, newState.getNUM(), 'H'); return; } else { for (int i = 1 ; i <= 4 ; ++i) { if (2 <= state[i].getNUM() && state[i].getNUM() <= 7) { set_instruction(nums, 1, getDirection[i - 1]); return; } } for (int i = 1 ; i <= 4 ; ++i) { if (state[i].getNUM() == 8) { set_instruction(nums, 1, getDirection[i - 1]); return; } } return; } } if (state[0].haventPassed) { if (state[1].isOutside && state[4].isOutside) { State newState = state[0]; newState.haventPassed = 0; newState.dep = 0; set_instruction(nums, newState.getNUM(), 'H'); return; } bool is[3] = {0, 0, 0}; for (int i = 1 ; i <= 4 ; ++i) { if (!state[i].haventPassed && !state[i].isCross && !state[i].isOutside) { is[state[i].dep] = 1; } } int cntAre = 0; cntAre += is[0]; cntAre += is[1]; cntAre += is[2]; if (cntAre == 0 || cntAre == 3) { return; } int parDep = -1; int myDep = -1; if (cntAre == 1) { if (is[0]) { parDep = 0; myDep = 1; } else if (is[1]) { parDep = 1; myDep = 2; } else { parDep = 2; myDep = 0; } } else { if (is[0] && is[1]) { parDep = 0; myDep = 1; } else if (is[0] && is[2]) { parDep = 2; myDep = 0; } else if (is[1] && is[2]) { parDep = 1; myDep = 2; } } int countCandidates = 0; for (int i = 1 ; i <= 4 ; ++i) { if (!state[i].haventPassed && !state[i].isCross && !state[i].isOutside && state[i].dep == parDep) { countCandidates++; } } assert(countCandidates); if (countCandidates == 1) { for (int i = 1 ; i <= 4 ; ++i) { if (!state[i].haventPassed && !state[i].isCross && !state[i].isOutside && state[i].dep == parDep) { State newState; newState.traversedThrough = 1; newState.dep = myDep; if (state[2].isOutside && state[3].isOutside) { newState.isOnStick = 1; } set_instruction(nums, newState.getNUM(), getDirection[i - 1]); return; } } assert(false); } else { for (int i = 1 ; i <= 4 ; ++i) { if (!state[i].haventPassed && !state[i].isCross && !state[i].isOutside && state[i].dep == parDep && state[i].traversedThrough) { State newState; newState.traversedThrough = 1; newState.dep = myDep; if (state[2].isOutside && state[3].isOutside) { newState.isOnStick = 1; } set_instruction(nums, newState.getNUM(), getDirection[i - 1]); return; } } return; assert(false); } } if (!state[0].traversedThrough) { char parent = 'H'; for (int i = 1 ; i <= 4 ; ++i) { if (state[i].isCross || state[i].isOutside || state[i].traversedThrough) { continue; } if (state[i].haventPassed) { State newState = state[0]; if (!(state[1].isOutside && state[4].isOutside)) { newState.traversedThrough = 1; } set_instruction(nums, newState.getNUM(), getDirection[i - 1]); return; } if (state[i].dep != (state[0].dep + 1) % 3) { parent = getDirection[i - 1]; } else { set_instruction(nums, state[0].getNUM(), getDirection[i - 1]); return; } } if (parent == 'H' && !(state[1].isOutside && state[4].isOutside)) { return; } State newState = state[0]; newState.traversedThrough = 1; set_instruction(nums, newState.getNUM(), parent); return; } if (!(state[1].isOutside && state[4].isOutside)) { bool isParentTraversed = false; for (int i = 1 ; i <= 4 ; ++i) { if (state[i].isCross || state[i].isOutside || state[i].haventPassed) { continue; } if (state[i].dep != (state[0].dep + 1) % 3) { isParentTraversed = state[i].traversedThrough; break; } } if (!isParentTraversed) { State newState = state[0]; newState.traversedThrough = 0; set_instruction(nums, newState.getNUM(), 'H'); return; } } char parent = 'H'; for (int i = 1 ; i <= 4 ; ++i) { if (state[i].isCross || state[i].isOutside || !state[i].traversedThrough) { continue; } if (state[i].haventPassed) { return; } if (state[i].dep != (state[0].dep + 1) % 3) { parent = getDirection[i - 1]; } else { set_instruction(nums, state[0].getNUM(), getDirection[i - 1]); return; } } if (parent == 'H' && !(state[1].isOutside && state[4].isOutside)) { return; } State newState = state[0]; newState.traversedThrough = 0; set_instruction(nums, newState.getNUM(), parent); return; } for (int curr = -2 ; curr <= Z_MAX ; ++curr) { state[idx].setState(curr); nums[idx] = curr; rec(idx + 1); } } void program_pulibot() { nums.resize(5); rec(0); }

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

robot.cpp: In constructor 'State::State()':
robot.cpp:26:56: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   26 |         isDone = traversedThrough = haventPassed = dep = isOutside = isCross = isOnStick = isClearing = 0;
      |                                                    ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
robot.cpp: In member function 'void State::setState(int)':
robot.cpp:42:56: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   42 |         isDone = traversedThrough = haventPassed = dep = isOutside = isCross = isOnStick = isClearing = 0;
      |                                                    ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...