oj.uz

Submission #55242

# Submission time Handle Problem Language Result Execution time Memory
55242 2018-07-06T17:28:49 Z Just_Solve_The_Problem Gondola (IOI14_gondola) C++11
55 / 100
 49 ms 10600 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()
#define ll long long

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 mod = (int)1e9 + 9;

int mult(ll a, ll b) {
  return (a * b) % mod;
}

ll binpow(ll a, ll n) {
  ll res = 1;
  while (n) {
    if (n & 1) {
      res = mult(res, a);
    }
    a = mult(a, a);
    n >>= 1;
  }
  return res;
}

int countReplacement(int n, int inputSeq[]) {
  if (!valid(n, inputSeq)) return 0;
  int res = 1;
  sort(inputSeq, inputSeq + n);
  for (int i = 0; i < n; i++) {
    if (inputSeq[i] <= n) continue;
    if (!i) {
      res = mult(res, binpow(n, inputSeq[i] - n - 1));
    } else {
      res = mult(res, binpow(n - i, inputSeq[i] - (max(inputSeq[i - 1], n)) - 1));
    }
  }
  if (inputSeq[0] > n) {
    res = mult(res, n);
  }
  return res;
}

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 376 KB Output is correct
3 Correct 3 ms 408 KB Output is correct
4 Correct 3 ms 408 KB Output is correct
5 Correct 2 ms 524 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 524 KB Output is correct
2 Correct 3 ms 532 KB Output is correct
3 Correct 2 ms 696 KB Output is correct
4 Correct 2 ms 732 KB Output is correct
5 Correct 2 ms 772 KB Output is correct
6 Correct 8 ms 1056 KB Output is correct
7 Correct 13 ms 1692 KB Output is correct
8 Correct 11 ms 2084 KB Output is correct
9 Correct 6 ms 2084 KB Output is correct
10 Correct 49 ms 2820 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2820 KB Output is correct
2 Correct 2 ms 2820 KB Output is correct
3 Correct 2 ms 2820 KB Output is correct
4 Correct 3 ms 2820 KB Output is correct
5 Correct 2 ms 2820 KB Output is correct
6 Correct 20 ms 2824 KB Output is correct
7 Correct 17 ms 3536 KB Output is correct
8 Correct 13 ms 3936 KB Output is correct
9 Correct 6 ms 3936 KB Output is correct
10 Correct 17 ms 4576 KB Output is correct
11 Correct 2 ms 4576 KB Output is correct
12 Correct 3 ms 4576 KB Output is correct
13 Correct 10 ms 4576 KB Output is correct
14 Correct 3 ms 4576 KB Output is correct
15 Correct 17 ms 5320 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6212 KB Output is correct
2 Correct 3 ms 6216 KB Output is correct
3 Correct 4 ms 6220 KB Output is correct
4 Correct 3 ms 6224 KB Output is correct
5 Correct 3 ms 6228 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6412 KB Output is correct
2 Correct 4 ms 6420 KB Output is correct
3 Correct 4 ms 6420 KB Output is correct
4 Correct 4 ms 6420 KB Output is correct
5 Correct 3 ms 6432 KB Output is correct
6 Correct 3 ms 6436 KB Output is correct
7 Correct 4 ms 6440 KB Output is correct
8 Correct 23 ms 6448 KB Output is correct
9 Correct 5 ms 6452 KB Output is correct
10 Correct 4 ms 6452 KB Output is correct
11 Correct 16 ms 7480 KB Output is correct
12 Correct 20 ms 8060 KB Output is correct
13 Correct 32 ms 8916 KB Output is correct
14 Correct 14 ms 8916 KB Output is correct
15 Correct 26 ms 10600 KB Output is correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 10600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 10600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 10600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 10600 KB Output isn't correct
2 Halted 0 ms 0 KB -