제출 #112995

#제출 시각아이디문제언어결과실행 시간메모리
112995model_codeWorld of Tank (innopolis2018_final_E)C++17
100 / 100
651 ms152640 KiB
#include <bits/stdc++.h> using namespace std; #define forn(i, n) for (int i = 0; i < int(n); i++) #define re return #define fi first #define mp make_pair #define se second #define sz(a) (int)a.size() #define prev previ #define tm tmmm #define div divv typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; const ll CMAX = ll(1e9); const int szk = 80000; ll n, m1, m2, t, bad[2000100][2], dp[2000100][2], dp2[2000100][2]; vector<pair<int, int> > pq; int main() { iostream::sync_with_stdio(0), cin.tie(0); pq.push_back(mp(1, -1)); cin >> n >> m1 >> m2 >> t; pq.push_back(mp(n, -1)); forn (i, m1) { int x; cin >> x; pq.push_back(mp(x, 0)); if (x < n) pq.push_back(mp(x + 1, -1)); } forn (i, m2) { int x; cin >> x; pq.push_back(mp(x, 1)); if (x < n) pq.push_back(mp(x + 1, -1)); } sort(pq.begin(), pq.end()); int qxx = 0; vector<int> c; forn (i, sz(pq)) { if (i == 0 || pq[i].fi != pq[i - 1].fi) { c.push_back(pq[i].fi); qxx++; } if (pq[i].se != -1) { bad[sz(c) - 1][pq[i].se] = 1; } } forn (i, sz(c)) { dp[i][0] = dp[i][1] = -ll(1e18); //dp2[i][0] = dp2[i][1] = -ll(1e18); } if (bad[0][0] == 0) { dp[0][0] = dp2[0][0] = 1; } if (bad[0][1] == 0) { dp[0][1] = dp2[0][0] = 1; } //cout << dp[0][1] << " " << dp[0][0] << "\n"; for (int i = 1; i < sz(c); i++) { forn (j, 2) { if (bad[i][j] == 0) { dp[i][j] = dp[i - 1][j] + c[i] - c[i - 1]; } if (bad[i][j]) { if (dp[i - 1][j] + c[i] - c[i - 1] - t >= 1) dp[i][j] = dp[i - 1][j] + c[i] - c[i - 1] - t; } } ll k1 = min(dp[i][0],t), k2 = min(dp[i][1], t); if (bad[i][1] == 0) dp[i][1] = max(dp[i][1], k1); if (bad[i][0] == 0) dp[i][0] = max(dp[i][0], k2); //cout << dp[i][0] << " " << dp[i][1] << "\n"; } if (dp[sz(c) - 1][0] < 0 && dp[sz(c) - 1][1] < 0) { cout << "No\n"; exit(0); } cout << "Yes\n"; vector<pair<int, int> > qx; vector<int> cp; vector<pair<int, int> > ps; int x = sz(c) - 1, y = 0; if (dp[sz(c) - 1][1] >= 0) y = 1; while (x > 0) { qx.push_back(mp(c[x], y)); cp.push_back(bad[x][y]); if (bad[x][y] == 0 && dp[x][y] == dp[x - 1][y] + c[x] - c[x - 1]) { x--; continue; } if (bad[x][y] == 1) { ps.push_back(mp(c[x], y)); x--; continue; } y ^= 1; continue; } vector<int> bl; qx.push_back(mp(c[x], y)); if (y == 1) { qx.push_back(mp(0, 1)); qx.push_back(mp(0, 0)); //bl.push_back(1); cp.push_back(0); cp.push_back(0); } bl.push_back(0); reverse(qx.begin(), qx.end()); reverse(cp.begin(), cp.end()); vector<int> nms; forn (i, sz(qx)) { if (i && qx[i].se != qx[i - 1].se) { bl.push_back(bl.back() + 1); nms.push_back(qx[i].fi); } else if(i)bl.push_back(bl.back()); } int qi = sz(cp); forn (i, sz(cp)) { if (cp[i]) { qi = i; break; } } vector<pair<int, int> > anss; int hv = 1; for (int i = 0; i < sz(qx); i++) { if (qx[i].fi == 0) continue; int psx = qx[i].fi, psy = qx[i].se; ll c = 0; //cout << hv << " " << qx[i].fi << " " << qx[i].se << " " << cp[i] << "\n"; while (qi < sz(cp) && bl[qi] == bl[i]) { psx += max(t - hv, 0LL); c += max(t - hv, 0LL); hv = 0; anss.push_back(mp(psx, psy + 1)); qi++; while (qi < sz(cp) && cp[qi] == 0) qi++; } if (i + 1 < sz(qx)) hv+= qx[i + 1].fi - qx[i].fi-c; assert(hv >= 0 || (i + 1 < sz(qx) && qx[i + 1].se == psy)); } cout << sz(nms) << "\n"; for (int v : nms) cout << v << " "; cout << "\n"; cout << sz(anss) << "\n"; for (auto v : anss) cout << v.fi << " " << v.se << "\n"; }
#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...