제출 #112995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
112995		model_code	World of Tank (innopolis2018_final_E)	C++17	100 / 100	651 ms	152640 KiB

E

#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";
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 27 / 27
• Subtask 5: 23 / 23