oj.uz

Submission #50780

# Submission time Handle Problem Language Result Execution time Memory
50780 2018-06-13T08:07:44 Z Just_Solve_The_Problem Gondola (IOI14_gondola) C++11
55 / 100
 24 ms 4196 KB 
#include <bits/stdc++.h>
#include "gondola.h"

using namespace std;

#define pb push_back
#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()

const int N = (int)3e5 + 7;

int valid(int n, int inputSeq[]) {
  int cnt = 1, start = -1;
  for (int i = 0; i < n; i++) {
    if (inputSeq[i] == cnt) {
      start = i;
      break;
    }
  }
  for (int i = start; i < n; i++) {
    if (inputSeq[i] != cnt) {
      return 0;
    }
    cnt++;
  }
  for (int i = 0; i < start; i++) {
    if (inputSeq[i] != cnt) {
      return 0;
    }
    cnt++;
  }
  return 1;
}

//----------------------

int has[N], pos[N];

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
  int start = -1, mx = -1;
  memset(pos, -1, sizeof pos);
  for (int i = 0; i < n; i++) {
    has[gondolaSeq[i]] = 1;
    pos[gondolaSeq[i]] = i;
    mx = max(mx, gondolaSeq[i]);
    if (gondolaSeq[i] <= n) {
      if (start != -1) continue;
      start = i - gondolaSeq[i] + 1;
      if (start < 0) start += n;
    }
  }
  deque < int > ans, dq;

  if (start == -1)
    start = 0;


  for (int i = n + 1; i <= mx; i++) {
    if (has[i]) {
      int qwe = pos[i];
      qwe -= start;
      if (qwe < 0) qwe += n;
      qwe++;
      ans.pb(qwe);
      while (!dq.empty()) {
        ans.pb(dq.front());
        dq.pop_front();
      }
      dq.clear();
    } else {
      dq.pb(i);
    }
  }

  int i = 0;
  for (int to : ans) {
    replacementSeq[i++] = to;
  }
  return i;
}

//----------------------

int countReplacement(int n, int inputSeq[])
{
  return -3;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 488 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 568 KB Output is correct
3 Correct 2 ms 568 KB Output is correct
4 Correct 2 ms 580 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 7 ms 740 KB Output is correct
7 Correct 13 ms 916 KB Output is correct
8 Correct 11 ms 916 KB Output is correct
9 Correct 5 ms 916 KB Output is correct
10 Correct 12 ms 916 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 916 KB Output is correct
2 Correct 2 ms 916 KB Output is correct
3 Correct 2 ms 916 KB Output is correct
4 Correct 2 ms 916 KB Output is correct
5 Correct 2 ms 916 KB Output is correct
6 Correct 6 ms 916 KB Output is correct
7 Correct 13 ms 916 KB Output is correct
8 Correct 11 ms 916 KB Output is correct
9 Correct 4 ms 916 KB Output is correct
10 Correct 12 ms 916 KB Output is correct
11 Correct 2 ms 916 KB Output is correct
12 Correct 2 ms 916 KB Output is correct
13 Correct 7 ms 916 KB Output is correct
14 Correct 2 ms 916 KB Output is correct
15 Correct 14 ms 916 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1764 KB Output is correct
2 Correct 3 ms 1768 KB Output is correct
3 Correct 3 ms 1768 KB Output is correct
4 Correct 3 ms 1768 KB Output is correct
5 Correct 3 ms 1768 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1768 KB Output is correct
2 Correct 3 ms 1768 KB Output is correct
3 Correct 3 ms 1768 KB Output is correct
4 Correct 3 ms 1872 KB Output is correct
5 Correct 3 ms 1900 KB Output is correct
6 Correct 3 ms 1900 KB Output is correct
7 Correct 3 ms 1900 KB Output is correct
8 Correct 3 ms 1900 KB Output is correct
9 Correct 3 ms 1900 KB Output is correct
10 Correct 3 ms 1900 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1900 KB Output is correct
2 Correct 3 ms 1900 KB Output is correct
3 Correct 3 ms 1900 KB Output is correct
4 Correct 3 ms 1900 KB Output is correct
5 Correct 3 ms 1900 KB Output is correct
6 Correct 2 ms 1900 KB Output is correct
7 Correct 3 ms 1900 KB Output is correct
8 Correct 3 ms 1900 KB Output is correct
9 Correct 3 ms 1900 KB Output is correct
10 Correct 3 ms 1900 KB Output is correct
11 Correct 13 ms 2348 KB Output is correct
12 Correct 14 ms 2476 KB Output is correct
13 Correct 17 ms 3200 KB Output is correct
14 Correct 13 ms 3200 KB Output is correct
15 Correct 24 ms 4196 KB Output is correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4196 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4196 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4196 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4196 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -