oj.uz

Submission #20608

# Submission time Handle Problem Language Result Execution time Memory
20608 2017-02-12T15:58:18 Z model_code Roller Coaster Railroad (IOI16_railroad) C++11
30 / 100
 169 ms 12196 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 0 ms 2024 KB n = 2
2 Correct 0 ms 2024 KB n = 2
3 Correct 0 ms 2024 KB n = 2
4 Correct 0 ms 2024 KB n = 2
5 Correct 0 ms 2024 KB n = 2
6 Incorrect 0 ms 2024 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 0 ms 2024 KB n = 2
2 Correct 0 ms 2024 KB n = 2
3 Correct 0 ms 2024 KB n = 2
4 Correct 0 ms 2024 KB n = 2
5 Correct 0 ms 2024 KB n = 2
6 Incorrect 0 ms 2024 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 166 ms 12196 KB n = 199999
2 Correct 116 ms 10452 KB n = 199991
3 Correct 113 ms 10452 KB n = 199993
4 Correct 123 ms 11248 KB n = 152076
5 Correct 66 ms 7028 KB n = 93249
6 Correct 143 ms 12192 KB n = 199910
7 Correct 139 ms 12196 KB n = 199999
8 Correct 159 ms 12196 KB n = 199997
9 Correct 129 ms 11632 KB n = 171294
10 Correct 126 ms 11028 KB n = 140872
11 Correct 143 ms 12192 KB n = 199886
12 Correct 169 ms 12196 KB n = 199996
13 Correct 136 ms 12196 KB n = 200000
14 Correct 119 ms 10452 KB n = 199998
15 Correct 106 ms 10452 KB n = 200000
16 Correct 109 ms 10452 KB n = 199998
17 Correct 116 ms 10452 KB n = 200000
18 Correct 113 ms 10292 KB n = 190000
19 Correct 123 ms 11752 KB n = 177777
20 Correct 73 ms 7152 KB n = 100000
21 Correct 143 ms 12196 KB n = 200000
22 Correct 119 ms 10452 KB n = 200000
23 Correct 139 ms 12196 KB n = 200000

Subtask #4
0 / 36.0

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