oj.uz

Submission #54588

# Submission time Handle Problem Language Result Execution time Memory
54588 2018-07-04T07:25:58 Z win11905 Gondola (IOI14_gondola) C++11
55 / 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;
}

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

int powMod(int a, int b) {
  if(!a) return a;
  if(!b) return 0;
  int val = 1;
  while(b) {
    if(b & 1) val = (1ll * val * a) % M;
    a = (1ll * 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]);
  if(V.size() == 1) return 1;
  long ans = 0; 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 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 544 KB Output is correct
2 Correct 2 ms 544 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 16 ms 2404 KB Output is correct
7 Correct 14 ms 2404 KB Output is correct
8 Correct 30 ms 4244 KB Output is correct
9 Correct 9 ms 4244 KB Output is correct
10 Correct 42 ms 4848 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 9404 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 9404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

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