이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
컴파일 시 표준 에러 (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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |