oj.uz

Submission #112994

# Submission time Handle Problem Language Result Execution time Memory
112994 2019-05-23T02:12:49 Z model_code World of Tank (innopolis2018_final_E) C++17
100 / 100
 302 ms 39720 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4224 KB [OK, Yes] n = 20, m1 = 20, m2 = 0, t = 20
2 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 509, m2 = 491, t = 5000
3 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 764, m2 = 736, t = 5000
4 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 698, m2 = 802, t = 5000
5 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 720, m2 = 780, t = 5000
6 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 734, m2 = 766, t = 5000
7 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 997, m2 = 1003, t = 5000
8 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 1021, m2 = 979, t = 5000
9 Correct 5 ms 4352 KB [OK, No] n = 5000, m1 = 1006, m2 = 995, t = 5000
10 Correct 6 ms 4352 KB [OK, No] n = 5000, m1 = 1017, m2 = 984, t = 5000
11 Correct 5 ms 4352 KB [OK, No] n = 5000, m1 = 1495, m2 = 1506, t = 5000

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4224 KB [OK, Yes] n = 20, m1 = 20, m2 = 0, t = 20
2 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 509, m2 = 491, t = 5000
3 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 764, m2 = 736, t = 5000
4 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 698, m2 = 802, t = 5000
5 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 720, m2 = 780, t = 5000
6 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 734, m2 = 766, t = 5000
7 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 997, m2 = 1003, t = 5000
8 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 1021, m2 = 979, t = 5000
9 Correct 5 ms 4352 KB [OK, No] n = 5000, m1 = 1006, m2 = 995, t = 5000
10 Correct 6 ms 4352 KB [OK, No] n = 5000, m1 = 1017, m2 = 984, t = 5000
11 Correct 5 ms 4352 KB [OK, No] n = 5000, m1 = 1495, m2 = 1506, t = 5000
12 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 974, m2 = 1026, t = 2501
13 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 1022, m2 = 978, t = 2501
14 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 1019, m2 = 981, t = 2501
15 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 1298, m2 = 1367, t = 2501
16 Correct 5 ms 4352 KB [OK, No] n = 5000, m1 = 1301, m2 = 1360, t = 2501
17 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 1320, m2 = 1315, t = 2501
18 Correct 5 ms 4352 KB [OK, No] n = 5000, m1 = 1195, m2 = 1135, t = 2501
19 Correct 5 ms 4352 KB [OK, No] n = 5000, m1 = 1148, m2 = 1202, t = 2501
20 Correct 5 ms 4352 KB [OK, No] n = 5000, m1 = 1147, m2 = 1179, t = 2501
21 Correct 6 ms 4352 KB [OK, No] n = 5000, m1 = 1163, m2 = 1146, t = 2501
22 Correct 5 ms 4352 KB [OK, No] n = 5000, m1 = 1145, m2 = 1184, t = 2501
23 Correct 5 ms 4324 KB [OK, No] n = 5000, m1 = 1172, m2 = 1150, t = 2501

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4224 KB [OK, Yes] n = 20, m1 = 12, m2 = 9, t = 3
2 Correct 5 ms 4224 KB [OK, Yes] n = 10, m1 = 4, m2 = 2, t = 2
3 Correct 4 ms 4224 KB [OK, Yes] n = 10, m1 = 6, m2 = 0, t = 2
4 Correct 5 ms 4352 KB [OK, Yes] n = 10, m1 = 2, m2 = 4, t = 1
5 Correct 5 ms 4352 KB [OK, No] n = 20, m1 = 4, m2 = 11, t = 2
6 Correct 5 ms 4352 KB [OK, Yes] n = 20, m1 = 7, m2 = 8, t = 1
7 Correct 4 ms 4352 KB [OK, Yes] n = 20, m1 = 7, m2 = 8, t = 2
8 Correct 3 ms 4224 KB [OK, Yes] n = 20, m1 = 0, m2 = 10, t = 2
9 Correct 2 ms 4352 KB [OK, Yes] n = 20, m1 = 4, m2 = 6, t = 2
10 Correct 5 ms 4352 KB [OK, Yes] n = 20, m1 = 9, m2 = 1, t = 2
11 Correct 5 ms 4352 KB [OK, Yes] n = 20, m1 = 10, m2 = 9, t = 2
12 Correct 5 ms 4352 KB [OK, Yes] n = 20, m1 = 9, m2 = 10, t = 2
13 Correct 4 ms 4224 KB [OK, Yes] n = 20, m1 = 0, m2 = 0, t = 3
14 Correct 5 ms 4352 KB [OK, Yes] n = 20, m1 = 5, m2 = 4, t = 3
15 Correct 5 ms 4224 KB [OK, Yes] n = 9, m1 = 4, m2 = 3, t = 3
16 Correct 5 ms 4352 KB [OK, Yes] n = 20, m1 = 8, m2 = 8, t = 3
17 Correct 5 ms 4352 KB [OK, Yes] n = 20, m1 = 9, m2 = 7, t = 3
18 Correct 5 ms 4268 KB [OK, Yes] n = 20, m1 = 9, m2 = 10, t = 7
19 Correct 5 ms 4352 KB [OK, Yes] n = 20, m1 = 7, m2 = 10, t = 8
20 Correct 5 ms 4352 KB [OK, Yes] n = 20, m1 = 13, m2 = 10, t = 4
21 Correct 4 ms 4224 KB [OK, Yes] n = 20, m1 = 9, m2 = 9, t = 8
22 Correct 4 ms 4224 KB [OK, Yes] n = 20, m1 = 10, m2 = 11, t = 3
23 Correct 5 ms 4224 KB [OK, Yes] n = 20, m1 = 11, m2 = 11, t = 3

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4224 KB [OK, Yes] n = 20, m1 = 20, m2 = 0, t = 20
2 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 509, m2 = 491, t = 5000
3 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 764, m2 = 736, t = 5000
4 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 698, m2 = 802, t = 5000
5 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 720, m2 = 780, t = 5000
6 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 734, m2 = 766, t = 5000
7 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 997, m2 = 1003, t = 5000
8 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 1021, m2 = 979, t = 5000
9 Correct 5 ms 4352 KB [OK, No] n = 5000, m1 = 1006, m2 = 995, t = 5000
10 Correct 6 ms 4352 KB [OK, No] n = 5000, m1 = 1017, m2 = 984, t = 5000
11 Correct 5 ms 4352 KB [OK, No] n = 5000, m1 = 1495, m2 = 1506, t = 5000
12 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 974, m2 = 1026, t = 2501
13 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 1022, m2 = 978, t = 2501
14 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 1019, m2 = 981, t = 2501
15 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 1298, m2 = 1367, t = 2501
16 Correct 5 ms 4352 KB [OK, No] n = 5000, m1 = 1301, m2 = 1360, t = 2501
17 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 1320, m2 = 1315, t = 2501
18 Correct 5 ms 4352 KB [OK, No] n = 5000, m1 = 1195, m2 = 1135, t = 2501
19 Correct 5 ms 4352 KB [OK, No] n = 5000, m1 = 1148, m2 = 1202, t = 2501
20 Correct 5 ms 4352 KB [OK, No] n = 5000, m1 = 1147, m2 = 1179, t = 2501
21 Correct 6 ms 4352 KB [OK, No] n = 5000, m1 = 1163, m2 = 1146, t = 2501
22 Correct 5 ms 4352 KB [OK, No] n = 5000, m1 = 1145, m2 = 1184, t = 2501
23 Correct 5 ms 4324 KB [OK, No] n = 5000, m1 = 1172, m2 = 1150, t = 2501
24 Correct 5 ms 4352 KB [OK, Yes] n = 500, m1 = 197, m2 = 53, t = 2
25 Correct 5 ms 4352 KB [OK, Yes] n = 500, m1 = 189, m2 = 61, t = 3
26 Correct 5 ms 4224 KB [OK, No] n = 500, m1 = 66, m2 = 184, t = 4
27 Correct 5 ms 4352 KB [OK, Yes] n = 500, m1 = 248, m2 = 252, t = 1
28 Correct 4 ms 4352 KB [OK, Yes] n = 500, m1 = 248, m2 = 252, t = 1
29 Correct 5 ms 4352 KB [OK, Yes] n = 500, m1 = 205, m2 = 295, t = 1
30 Correct 51 ms 10224 KB [OK, Yes] n = 1000000, m1 = 183472, m2 = 66528, t = 7
31 Correct 49 ms 9372 KB [OK, Yes] n = 1000000, m1 = 206211, m2 = 43789, t = 6
32 Correct 43 ms 8820 KB [OK, Yes] n = 1000000, m1 = 229445, m2 = 20555, t = 7
33 Correct 69 ms 8184 KB [OK, No] n = 1000000, m1 = 261335, m2 = 238665, t = 2
34 Correct 93 ms 14700 KB [OK, Yes] n = 1000000, m1 = 374819, m2 = 125181, t = 3
35 Correct 86 ms 14316 KB [OK, Yes] n = 1000000, m1 = 88376, m2 = 411624, t = 3
36 Correct 5 ms 4352 KB [OK, Yes] n = 500, m1 = 125, m2 = 125, t = 2
37 Correct 108 ms 17260 KB [OK, Yes] n = 1000000, m1 = 250000, m2 = 250000, t = 2
38 Correct 41 ms 8560 KB [OK, Yes] n = 1000000, m1 = 94957, m2 = 94938, t = 12
39 Correct 43 ms 9628 KB [OK, Yes] n = 1000000, m1 = 94972, m2 = 95007, t = 10
40 Correct 10 ms 4992 KB [OK, Yes] n = 1000000, m1 = 14064, m2 = 13936, t = 200
41 Correct 10 ms 4992 KB [OK, Yes] n = 1000000, m1 = 15990, m2 = 16010, t = 139
42 Correct 17 ms 5856 KB [OK, Yes] n = 1000000, m1 = 32291, m2 = 32404, t = 34
43 Correct 36 ms 8168 KB [OK, Yes] n = 1000000, m1 = 88230, m2 = 88238, t = 13
44 Correct 22 ms 6308 KB [OK, Yes] n = 1000000, m1 = 44550, m2 = 44400, t = 34
45 Correct 17 ms 5756 KB [OK, Yes] n = 1000000, m1 = 31778, m2 = 31772, t = 44
46 Correct 39 ms 6520 KB [OK, No] n = 1000000, m1 = 147142, m2 = 147242, t = 10
47 Correct 5 ms 4352 KB [OK, Yes] n = 1000, m1 = 416, m2 = 417, t = 77
48 Correct 5 ms 4352 KB [OK, Yes] n = 1000, m1 = 412, m2 = 414, t = 111
49 Correct 5 ms 4352 KB [OK, Yes] n = 1000, m1 = 422, m2 = 423, t = 62
50 Correct 5 ms 4352 KB [OK, Yes] n = 800, m1 = 279, m2 = 270, t = 33

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4224 KB [OK, Yes] n = 20, m1 = 20, m2 = 0, t = 20
2 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 509, m2 = 491, t = 5000
3 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 764, m2 = 736, t = 5000
4 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 698, m2 = 802, t = 5000
5 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 720, m2 = 780, t = 5000
6 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 734, m2 = 766, t = 5000
7 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 997, m2 = 1003, t = 5000
8 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 1021, m2 = 979, t = 5000
9 Correct 5 ms 4352 KB [OK, No] n = 5000, m1 = 1006, m2 = 995, t = 5000
10 Correct 6 ms 4352 KB [OK, No] n = 5000, m1 = 1017, m2 = 984, t = 5000
11 Correct 5 ms 4352 KB [OK, No] n = 5000, m1 = 1495, m2 = 1506, t = 5000
12 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 974, m2 = 1026, t = 2501
13 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 1022, m2 = 978, t = 2501
14 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 1019, m2 = 981, t = 2501
15 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 1298, m2 = 1367, t = 2501
16 Correct 5 ms 4352 KB [OK, No] n = 5000, m1 = 1301, m2 = 1360, t = 2501
17 Correct 5 ms 4352 KB [OK, Yes] n = 5000, m1 = 1320, m2 = 1315, t = 2501
18 Correct 5 ms 4352 KB [OK, No] n = 5000, m1 = 1195, m2 = 1135, t = 2501
19 Correct 5 ms 4352 KB [OK, No] n = 5000, m1 = 1148, m2 = 1202, t = 2501
20 Correct 5 ms 4352 KB [OK, No] n = 5000, m1 = 1147, m2 = 1179, t = 2501
21 Correct 6 ms 4352 KB [OK, No] n = 5000, m1 = 1163, m2 = 1146, t = 2501
22 Correct 5 ms 4352 KB [OK, No] n = 5000, m1 = 1145, m2 = 1184, t = 2501
23 Correct 5 ms 4324 KB [OK, No] n = 5000, m1 = 1172, m2 = 1150, t = 2501
24 Correct 5 ms 4224 KB [OK, Yes] n = 20, m1 = 12, m2 = 9, t = 3
25 Correct 5 ms 4224 KB [OK, Yes] n = 10, m1 = 4, m2 = 2, t = 2
26 Correct 4 ms 4224 KB [OK, Yes] n = 10, m1 = 6, m2 = 0, t = 2
27 Correct 5 ms 4352 KB [OK, Yes] n = 10, m1 = 2, m2 = 4, t = 1
28 Correct 5 ms 4352 KB [OK, No] n = 20, m1 = 4, m2 = 11, t = 2
29 Correct 5 ms 4352 KB [OK, Yes] n = 20, m1 = 7, m2 = 8, t = 1
30 Correct 4 ms 4352 KB [OK, Yes] n = 20, m1 = 7, m2 = 8, t = 2
31 Correct 3 ms 4224 KB [OK, Yes] n = 20, m1 = 0, m2 = 10, t = 2
32 Correct 2 ms 4352 KB [OK, Yes] n = 20, m1 = 4, m2 = 6, t = 2
33 Correct 5 ms 4352 KB [OK, Yes] n = 20, m1 = 9, m2 = 1, t = 2
34 Correct 5 ms 4352 KB [OK, Yes] n = 20, m1 = 10, m2 = 9, t = 2
35 Correct 5 ms 4352 KB [OK, Yes] n = 20, m1 = 9, m2 = 10, t = 2
36 Correct 4 ms 4224 KB [OK, Yes] n = 20, m1 = 0, m2 = 0, t = 3
37 Correct 5 ms 4352 KB [OK, Yes] n = 20, m1 = 5, m2 = 4, t = 3
38 Correct 5 ms 4224 KB [OK, Yes] n = 9, m1 = 4, m2 = 3, t = 3
39 Correct 5 ms 4352 KB [OK, Yes] n = 20, m1 = 8, m2 = 8, t = 3
40 Correct 5 ms 4352 KB [OK, Yes] n = 20, m1 = 9, m2 = 7, t = 3
41 Correct 5 ms 4268 KB [OK, Yes] n = 20, m1 = 9, m2 = 10, t = 7
42 Correct 5 ms 4352 KB [OK, Yes] n = 20, m1 = 7, m2 = 10, t = 8
43 Correct 5 ms 4352 KB [OK, Yes] n = 20, m1 = 13, m2 = 10, t = 4
44 Correct 4 ms 4224 KB [OK, Yes] n = 20, m1 = 9, m2 = 9, t = 8
45 Correct 4 ms 4224 KB [OK, Yes] n = 20, m1 = 10, m2 = 11, t = 3
46 Correct 5 ms 4224 KB [OK, Yes] n = 20, m1 = 11, m2 = 11, t = 3
47 Correct 5 ms 4352 KB [OK, Yes] n = 500, m1 = 197, m2 = 53, t = 2
48 Correct 5 ms 4352 KB [OK, Yes] n = 500, m1 = 189, m2 = 61, t = 3
49 Correct 5 ms 4224 KB [OK, No] n = 500, m1 = 66, m2 = 184, t = 4
50 Correct 5 ms 4352 KB [OK, Yes] n = 500, m1 = 248, m2 = 252, t = 1
51 Correct 4 ms 4352 KB [OK, Yes] n = 500, m1 = 248, m2 = 252, t = 1
52 Correct 5 ms 4352 KB [OK, Yes] n = 500, m1 = 205, m2 = 295, t = 1
53 Correct 51 ms 10224 KB [OK, Yes] n = 1000000, m1 = 183472, m2 = 66528, t = 7
54 Correct 49 ms 9372 KB [OK, Yes] n = 1000000, m1 = 206211, m2 = 43789, t = 6
55 Correct 43 ms 8820 KB [OK, Yes] n = 1000000, m1 = 229445, m2 = 20555, t = 7
56 Correct 69 ms 8184 KB [OK, No] n = 1000000, m1 = 261335, m2 = 238665, t = 2
57 Correct 93 ms 14700 KB [OK, Yes] n = 1000000, m1 = 374819, m2 = 125181, t = 3
58 Correct 86 ms 14316 KB [OK, Yes] n = 1000000, m1 = 88376, m2 = 411624, t = 3
59 Correct 5 ms 4352 KB [OK, Yes] n = 500, m1 = 125, m2 = 125, t = 2
60 Correct 108 ms 17260 KB [OK, Yes] n = 1000000, m1 = 250000, m2 = 250000, t = 2
61 Correct 41 ms 8560 KB [OK, Yes] n = 1000000, m1 = 94957, m2 = 94938, t = 12
62 Correct 43 ms 9628 KB [OK, Yes] n = 1000000, m1 = 94972, m2 = 95007, t = 10
63 Correct 10 ms 4992 KB [OK, Yes] n = 1000000, m1 = 14064, m2 = 13936, t = 200
64 Correct 10 ms 4992 KB [OK, Yes] n = 1000000, m1 = 15990, m2 = 16010, t = 139
65 Correct 17 ms 5856 KB [OK, Yes] n = 1000000, m1 = 32291, m2 = 32404, t = 34
66 Correct 36 ms 8168 KB [OK, Yes] n = 1000000, m1 = 88230, m2 = 88238, t = 13
67 Correct 22 ms 6308 KB [OK, Yes] n = 1000000, m1 = 44550, m2 = 44400, t = 34
68 Correct 17 ms 5756 KB [OK, Yes] n = 1000000, m1 = 31778, m2 = 31772, t = 44
69 Correct 39 ms 6520 KB [OK, No] n = 1000000, m1 = 147142, m2 = 147242, t = 10
70 Correct 5 ms 4352 KB [OK, Yes] n = 1000, m1 = 416, m2 = 417, t = 77
71 Correct 5 ms 4352 KB [OK, Yes] n = 1000, m1 = 412, m2 = 414, t = 111
72 Correct 5 ms 4352 KB [OK, Yes] n = 1000, m1 = 422, m2 = 423, t = 62
73 Correct 5 ms 4352 KB [OK, Yes] n = 800, m1 = 279, m2 = 270, t = 33
74 Correct 8 ms 4352 KB [OK, Yes] n = 1000000000, m1 = 489, m2 = 511, t = 3000000
75 Correct 5 ms 4352 KB [OK, Yes] n = 100000000, m1 = 496, m2 = 504, t = 300000
76 Correct 5 ms 4352 KB [OK, Yes] n = 100000000, m1 = 506, m2 = 494, t = 400000
77 Correct 5 ms 4352 KB [OK, Yes] n = 100000000, m1 = 520, m2 = 480, t = 230000
78 Correct 6 ms 4352 KB [OK, Yes] n = 1000000000, m1 = 995, m2 = 1005, t = 1100000
79 Correct 5 ms 4352 KB [OK, Yes] n = 1000000000, m1 = 1016, m2 = 984, t = 1100003
80 Correct 212 ms 29412 KB [OK, Yes] n = 10000000, m1 = 423780, m2 = 576220, t = 1
81 Correct 171 ms 22384 KB [OK, Yes] n = 10000000, m1 = 102640, m2 = 897360, t = 16
82 Correct 293 ms 39544 KB [OK, Yes] n = 10000000, m1 = 922340, m2 = 77660, t = 6
83 Correct 152 ms 21996 KB [OK, Yes] n = 10000000, m1 = 66539, m2 = 933461, t = 5
84 Correct 176 ms 24296 KB [OK, Yes] n = 10000000, m1 = 156107, m2 = 843893, t = 17
85 Correct 302 ms 39720 KB [OK, Yes] n = 1000000000, m1 = 950948, m2 = 49052, t = 297
86 Correct 209 ms 28388 KB [OK, Yes] n = 1000000000, m1 = 288017, m2 = 711983, t = 1174
87 Correct 177 ms 22384 KB [OK, Yes] n = 1000000000, m1 = 103443, m2 = 896557, t = 1547
88 Correct 168 ms 21124 KB [OK, Yes] n = 1000000000, m1 = 51412, m2 = 948588, t = 1440
89 Correct 191 ms 24616 KB [OK, Yes] n = 1000000000, m1 = 192898, m2 = 807102, t = 581
90 Correct 211 ms 30052 KB [OK, Yes] n = 1000000000, m1 = 500000, m2 = 500000, t = 2
91 Correct 208 ms 27592 KB [OK, Yes] n = 1000000000, m1 = 499558, m2 = 500434, t = 2500
92 Correct 204 ms 26884 KB [OK, Yes] n = 1000000000, m1 = 496969, m2 = 497436, t = 3000
93 Correct 194 ms 25552 KB [OK, Yes] n = 1000000000, m1 = 444326, m2 = 444763, t = 4000
94 Correct 142 ms 12232 KB [OK, No] n = 1000000000, m1 = 499655, m2 = 500345, t = 2000
95 Correct 193 ms 24744 KB [OK, Yes] n = 1000000000, m1 = 423266, m2 = 423367, t = 4500
96 Correct 145 ms 12032 KB [OK, No] n = 1000000000, m1 = 499763, m2 = 500237, t = 3500
97 Correct 186 ms 24268 KB [OK, Yes] n = 1000000000, m1 = 404552, m2 = 404965, t = 5000