oj.uz

Submission #54597

# Submission time Handle Problem Language Result Execution time Memory
54597 2018-07-04T07:38:23 Z win11905 Gondola (IOI14_gondola) C++11
75 / 100
 67 ms 9404 KB 
#include <bits/stdc++.h>
#define long long long
#include "gondola.h"
using namespace std;

const long M = 1e9+9;

int valid(int n, int inputSeq[]) {
  map<int, int> M;
  for(int i = 0, st = -n-1; i < n; ++i, ++st) {
    M[inputSeq[i]]++;
    if(st == n+1) st = 1;
    if(inputSeq[i] <= n) {
      if(st < 0) st = inputSeq[i];
      else if(st != inputSeq[i]) return 0;
    }
  }
  for(auto x : M) if(x.second > 1) return 0;
  return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
  int sz = 0, shift = 0;
  for(int i = 0; i < n; ++i) if(gondolaSeq[i] <= n) shift = i - gondolaSeq[i] + 1;
  vector<int> ret(n);
  for(int i = 0; i < n; ++i) ret[i] = gondolaSeq[(i + shift + n) % n];
  int pos = max_element(ret.begin(), ret.end()) - ret.begin() + 1;
  int mx = *max_element(ret.begin(), ret.end());
  map<int, int> M;
  for(int i = 0; i < n; ++i) if(ret[i] > n) M[ret[i]] = i+1;
  for(int i = n+1; i <= mx; ++i) {
    if(M[i] == 0 || i == mx) replacementSeq[sz++] = pos, pos = i;
    else replacementSeq[sz++] = M[i];
  }
  return sz;
}

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

long powMod(long a, long b) {
  long val = 1;
  while(b) {
    if(b & 1) val = (val * a) % M;
    a = (a * a) % M;
    b >>= 1;
  }
  return val;
}

int countReplacement(int n, int inputSeq[]) {
  if(!valid(n, inputSeq)) return 0;
  vector<int> V; V.emplace_back(n);
  for(int i = 0; i < n; ++i) if(inputSeq[i] > n) V.emplace_back(inputSeq[i]);
  long ans = 1; int s = V.size();
  sort(V.begin(), V.end());
  for(int i = 1; i < s; ++i) ans = (ans * powMod(s - i, V[i] - V[i-1] - 1)) % M;
  return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 432 KB Output is correct
5 Correct 2 ms 456 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 456 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 2 ms 536 KB Output is correct
5 Correct 3 ms 660 KB Output is correct
6 Correct 21 ms 2508 KB Output is correct
7 Correct 13 ms 2508 KB Output is correct
8 Correct 29 ms 4316 KB Output is correct
9 Correct 10 ms 4316 KB Output is correct
10 Correct 37 ms 4796 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9404 KB Output is correct
2 Correct 2 ms 9404 KB Output is correct
3 Correct 2 ms 9404 KB Output is correct

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9404 KB Output is correct
2 Correct 2 ms 9404 KB Output is correct
3 Correct 2 ms 9404 KB Output is correct
4 Correct 2 ms 9404 KB Output is correct
5 Correct 2 ms 9404 KB Output is correct
6 Correct 2 ms 9404 KB Output is correct
7 Correct 2 ms 9404 KB Output is correct
8 Correct 2 ms 9404 KB Output is correct
9 Correct 52 ms 9404 KB Output is correct
10 Correct 39 ms 9404 KB Output is correct
11 Correct 15 ms 9404 KB Output is correct
12 Correct 19 ms 9404 KB Output is correct
13 Incorrect 5 ms 9404 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9404 KB Output is correct
2 Correct 2 ms 9404 KB Output is correct
3 Correct 2 ms 9404 KB Output is correct
4 Correct 2 ms 9404 KB Output is correct
5 Correct 2 ms 9404 KB Output is correct
6 Correct 2 ms 9404 KB Output is correct
7 Correct 3 ms 9404 KB Output is correct
8 Correct 2 ms 9404 KB Output is correct
9 Correct 52 ms 9404 KB Output is correct
10 Correct 51 ms 9404 KB Output is correct
11 Correct 16 ms 9404 KB Output is correct
12 Correct 19 ms 9404 KB Output is correct
13 Incorrect 5 ms 9404 KB Output isn't correct
14 Halted 0 ms 0 KB -