oj.uz

Submission #730324

# Submission time Handle Problem Language Result Execution time Memory
730324 2023-04-25T17:25:06 Z ktkerem Roller Coaster Railroad (IOI16_railroad) C++17
30 / 100
 132 ms 13084 KB 
// name = railroad_ak.cpp, type = cpp.g++11

#include "railroad.h"
#include <bits/stdc++.h>
 
#define SZ(AA) ((int)((AA).size()))
#define ALL(AA) (AA).begin(), (AA).end()
 
using namespace std;
 
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef long long LL;
typedef long double LD;
 
LL plan_roller_coaster(vector<int> s, vector<int> t) {
  int n = SZ(s);
  vector<PII> a, b;
  a.push_back({1, -1});
  b.push_back({max(*max_element(ALL(s)), *max_element(ALL(t))), n});
  for (int i = 0; i < n; ++i) {
    a.push_back({t[i], i});
    b.push_back({s[i], i});
  }
  sort(ALL(a));
  sort(ALL(b));
  for (int i = 0; i < SZ(a); ++i) {
    if (a[i].first > b[i].first) {
      return 1;
    }
  }
  VI ra(n);
  for (int i = 0; i < SZ(a); ++i) {
    if (a[i].second >= 0 && a[i].second < n) {
      ra[a[i].second] = i;
    }
  }
  vector<bool> vis(SZ(a));
  VI Q;
  vis[0] = true; Q.push_back(0);
  for (int i = 0; i < SZ(Q); ++i) {
    int v = Q[i];
    VI can;
    if (b[v].second != n) {
      can.push_back(ra[b[v].second]);
    }
    if (v > 0 && b[v - 1].first >= a[v].first) {
      can.push_back(v - 1);
    }
    if (v < SZ(a) - 1 && b[v].first >= a[v + 1].first) {
      can.push_back(v + 1);
    }
    for (int w : can) {
      if (!vis[w]) {
        vis[w] = true;
        Q.push_back(w);
      }
    }
  }
  return SZ(Q) == SZ(a) ? 0 : 1;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 1 ms 212 KB n = 2
4 Correct 1 ms 296 KB n = 2
5 Correct 1 ms 212 KB n = 2
6 Incorrect 0 ms 212 KB answer is not correct: 1 instead of 523688153
7 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 1 ms 212 KB n = 2
4 Correct 1 ms 296 KB n = 2
5 Correct 1 ms 212 KB n = 2
6 Incorrect 0 ms 212 KB answer is not correct: 1 instead of 523688153
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 13012 KB n = 199999
2 Correct 81 ms 10552 KB n = 199991
3 Correct 77 ms 10656 KB n = 199993
4 Correct 80 ms 9840 KB n = 152076
5 Correct 45 ms 6280 KB n = 93249
6 Correct 95 ms 11928 KB n = 199910
7 Correct 102 ms 12424 KB n = 199999
8 Correct 98 ms 11948 KB n = 199997
9 Correct 100 ms 11196 KB n = 171294
10 Correct 84 ms 9580 KB n = 140872
11 Correct 100 ms 11892 KB n = 199886
12 Correct 97 ms 12328 KB n = 199996
13 Correct 105 ms 11932 KB n = 200000
14 Correct 79 ms 9784 KB n = 199998
15 Correct 80 ms 9760 KB n = 200000
16 Correct 85 ms 10136 KB n = 199998
17 Correct 78 ms 10664 KB n = 200000
18 Correct 80 ms 10296 KB n = 190000
19 Correct 87 ms 11752 KB n = 177777
20 Correct 49 ms 6584 KB n = 100000
21 Correct 121 ms 13084 KB n = 200000
22 Correct 105 ms 11172 KB n = 200000
23 Correct 97 ms 12952 KB n = 200000

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 1 ms 212 KB n = 2
4 Correct 1 ms 296 KB n = 2
5 Correct 1 ms 212 KB n = 2
6 Incorrect 0 ms 212 KB answer is not correct: 1 instead of 523688153
7 Halted 0 ms 0 KB -