Submission #112994

#TimeUsernameProblemLanguageResultExecution timeMemory
112994model_codeWorld of Tank (innopolis2018_final_E)C++17
100 / 100
302 ms39720 KiB
#include <algorithm> #include <cstdio> #include <cstring> #include <iostream> #include <vector> using namespace std; const int MAXM = (int) 2e6 + 10; int n, m[2], t; int blocks[2][MAXM]; int dp[2][MAXM]; int prevTurn[2][MAXM]; bool wasTurn[2][MAXM]; int wasBlowed[2][MAXM]; int pos[2], firstInLine[2]; bool nextEmpty(int tp) { if (pos[tp] == m[tp]) { return false; } return blocks[tp][pos[tp]] + 1 != blocks[tp][pos[tp] + 1]; } bool prevEmpty(int tp) { if (pos[tp] == 0) { return false; } return blocks[tp][pos[tp]] - 1 != blocks[tp][pos[tp] - 1]; } void updateFirst(int tp) { if (prevEmpty(tp)) { firstInLine[tp] = pos[tp]; } } void updateByBlowing(int tp) { int v = firstInLine[tp] - 1; if (dp[tp][v] == -1) { return; } int val = dp[tp][v] + blocks[tp][firstInLine[tp]] - blocks[tp][v] - 2; int blow_len = pos[tp] - firstInLine[tp] + 1; if ((val + blow_len - 1) / t < blow_len) { return; } int cans = val + blow_len + 1 - blow_len * t; if (cans <= dp[tp][pos[tp]]) { return; } dp[tp][pos[tp]] = cans; wasTurn[tp][pos[tp]] = false; if (wasTurn[tp][v]) { prevTurn[tp][pos[tp]] = v; wasBlowed[tp][pos[tp]] = blow_len; } else { prevTurn[tp][pos[tp]] = prevTurn[tp][v]; wasBlowed[tp][pos[tp]] = wasBlowed[tp][v] + blow_len; } } void updateNeighbor(int tp) { if (dp[1 - tp][pos[1 - tp]] == -1 || dp[tp][pos[tp]] >= min(dp[1 - tp][pos[1 - tp]], t)) { return; } dp[tp][pos[tp]] = min(dp[1 - tp][pos[1 - tp]], t); wasTurn[tp][pos[tp]] = true; prevTurn[tp][pos[tp]] = pos[1 - tp]; wasBlowed[tp][pos[tp]] = 0; } void updateTwoNeighbors() { updateByBlowing(0); updateByBlowing(1); updateNeighbor(0); updateNeighbor(1); } void update(int tp) { if (!nextEmpty(tp)) { ++pos[tp]; return; } updateByBlowing(tp); if (blocks[1 - tp][pos[1 - tp]] - blocks[tp][pos[tp]] >= 2) { int v = firstInLine[1 - tp] - 1; if (dp[1 - tp][v] == -1) { ++pos[tp]; return; } int val = dp[1 - tp][v] + blocks[tp][pos[tp]] - blocks[1 - tp][v]; int cans = min(t, val); if (cans > dp[tp][pos[tp]]) { dp[tp][pos[tp]] = cans; wasTurn[tp][pos[tp]] = true; if (wasTurn[1 - tp][v]) { prevTurn[tp][pos[tp]] = v; wasBlowed[tp][pos[tp]] = 0; } else { prevTurn[tp][pos[tp]] = prevTurn[1 - tp][v]; wasBlowed[tp][pos[tp]] = wasBlowed[1 - tp][v]; } } } else { int v = firstInLine[1 - tp] - 1; int ff = firstInLine[1 - tp]; int blow_len = blocks[tp][pos[tp]] - blocks[1 - tp][ff] + 2; if (dp[1 - tp][v] == -1) { ++pos[tp]; return; } int val = dp[1 - tp][v] + blocks[1 - tp][ff] - blocks[1 - tp][v] - 2; if ((val + blow_len - 1) / t >= blow_len) { int cans = val + blow_len - blow_len * t; cans = min(cans, t); if (cans > dp[tp][pos[tp]]) { dp[tp][pos[tp]] = cans; wasTurn[tp][pos[tp]] = true; if (wasTurn[1 - tp][v]) { prevTurn[tp][pos[tp]] = v; wasBlowed[tp][pos[tp]] = blow_len; } else { prevTurn[tp][pos[tp]] = prevTurn[1 - tp][v]; wasBlowed[tp][pos[tp]] = wasBlowed[1 - tp][v] + blow_len; } } } } ++pos[tp]; } bool answerYes() { return dp[0][m[0] - 1] != -1 || dp[1][m[1] - 1] != -1; } void restoreAns(vector<int>& turns, vector<pair<int, int>>& shots) { int tp; if (dp[0][m[0] - 1] != -1) { tp = 0; } else { tp = 1; } int ps = m[tp] - 1; while (ps != -1) { vector<pair<int, int>> cur_shots; if (wasTurn[tp][ps]) { turns.push_back(blocks[tp][ps] + 1); int nxt = prevTurn[tp][ps]; int cpos; if (nxt == -1) { cpos = t; } else { cpos = blocks[1 - tp][nxt] + 1 + t - dp[1 - tp][nxt]; } int blow_len = wasBlowed[tp][ps]; for (int i = 0; i < blow_len; ++i) { cur_shots.push_back({2 - tp, cpos}); cpos += t; } ps = nxt; tp = 1 - tp; } else { int nxt = prevTurn[tp][ps]; int cpos; if (nxt == -1) { cpos = t; } else { cpos = blocks[tp][nxt] + 1 + t - dp[tp][nxt]; } int blow_len = wasBlowed[tp][ps]; for (int i = 0; i < blow_len; ++i) { cur_shots.push_back({tp + 1, cpos}); cpos += t; } ps = nxt; } int sz = cur_shots.size(); for (int i = sz - 1; i >= 0; --i) { shots.push_back(cur_shots[i]); } } reverse(shots.begin(), shots.end()); reverse(turns.begin(), turns.end()); } int main() { scanf("%d%d%d%d", &n, &m[0], &m[1], &t); for (int i = 0; i < 2; ++i) { blocks[i][0] = -1; for (int j = 0; j < m[i]; ++j) { scanf("%d", &blocks[i][j + 1]); } } blocks[0][m[0] + 1] = n + 2; blocks[1][m[1] + 1] = n + 2; m[0]++; m[1]++; memset(wasTurn, 0, sizeof(wasTurn)); dp[0][0] = 0; dp[1][0] = 0; prevTurn[0][0] = -1; prevTurn[1][0] = 0; wasTurn[0][0] = false; wasTurn[1][0] = true; wasBlowed[0][0] = 0; wasBlowed[1][0] = 0; pos[0] = pos[1] = 1; while (pos[0] < m[0] || pos[1] < m[1]) { updateFirst(0); updateFirst(1); dp[0][pos[0]] = dp[1][pos[1]] = -1; if (blocks[0][pos[0]] < blocks[1][pos[1]]) { update(0); continue; } if (blocks[0][pos[0]] > blocks[1][pos[1]]) { update(1); continue; } if (nextEmpty(0) == nextEmpty(1)) { if (nextEmpty(0)) { updateTwoNeighbors(); } ++pos[0]; ++pos[1]; } else { if (nextEmpty(0)) { update(0); } else { update(1); } } } if (!answerYes()) { printf("No\n"); return 0; } printf("Yes\n"); vector<int> turns; vector<pair<int, int>> shots; restoreAns(turns, shots); int tsz = turns.size(); printf("%d\n", tsz); for (int i = 0; i < tsz; ++i) { printf("%d ", turns[i]); } printf("\n"); tsz = shots.size(); printf("%d\n", tsz); for (int i = 0; i < tsz; ++i) { printf("%d %d\n", shots[i].second, shots[i].first); } return 0; }

Compilation message (stderr)

E.cpp: In function 'int main()':
E.cpp:206:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &n, &m[0], &m[1], &t);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
E.cpp:210:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &blocks[i][j + 1]);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...