Submission #112994

#	Time	Username	Problem	Language	Result	Execution time	Memory
112994		model_code	World of Tank (innopolis2018_final_E)	C++17	100 / 100	302 ms	39720 KiB

E

#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]);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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