Submission #1035625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035625		vjudge1	World of Tank (innopolis2018_final_E)	C++17	30 / 100	1 ms	348 KiB

E

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+2;

int n, m0, m1, t;
queue<int> q[2];
bitset<N> obstacle[2];
vector<int> c;
vector<pair<int, int>> s;

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m0 >> m1 >> t;
  for (int i = 0; i < m0; i++) {
    int x; cin >> x;
    q[0].push(x);
    obstacle[0][x] = 1;
  }
  for (int i = 0; i < m1; i++) {
    int x; cin >> x;
    q[1].push(x);
    obstacle[1][x] = 1;
  }

  bool ok = 1; // can i reach the end?
  int lane = 0; // in which line am i
  int lastX = 0; // first x since the lane change
  int lastShot = 0; // when was the last shot
  for (int i = 0; i < n+1; i++) {
    //cerr << i << " " << ok << " " << lane << " " << lastX << " " << lastShot << endl;
    while (!q[lane].empty() && q[lane].front() <= i) q[lane].pop();
    while (!q[!lane].empty() && q[!lane].front() < i) q[!lane].pop();

    while (!q[0].empty() && !q[1].empty() && q[0].front() == q[1].front()) {
      q[0].pop();
      q[1].pop();
    }
    
    // cambio de linea?
    if (!obstacle[!lane][i] && !q[lane].empty() && (q[!lane].empty() || q[!lane].front() > q[lane].front())) {
      c.push_back(i);
      lane = !lane;
      lastX = i;
    }

    // disparo?
    if (obstacle[lane][i+1]) {
      int x = max(lastX, lastShot+t);
      if (x > i) {
        ok = 0;
        break;
      }
      else {
        s.push_back(make_pair(x, lane));
        lastShot = x;
      }
    }
  }

  if (!ok) {
    cout << "No\n";
  }
  else {
    cout << "Yes\n";

    int sz = c.size();
    cout << sz << "\n";
    for (int& i : c) cout << i << " ";
    cout << "\n";

    sz = s.size();
    cout << sz << "\n";
    for (auto& [i, j] : s) cout << i << " " << j+1 << "\n";
  }
}

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