oj.uz

답안 #54594

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
54594 2018-07-04T07:35:11 Z win11905 곤돌라 (IOI14_gondola) C++11
75 / 100
 66 ms 9388 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) {
  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]);
  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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 484 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 484 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 484 KB Output is correct
6 Correct 16 ms 2364 KB Output is correct
7 Correct 13 ms 2364 KB Output is correct
8 Correct 27 ms 4116 KB Output is correct
9 Correct 10 ms 4116 KB Output is correct
10 Correct 37 ms 4820 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4820 KB Output is correct
2 Correct 2 ms 4820 KB Output is correct
3 Correct 2 ms 4820 KB Output is correct
4 Correct 2 ms 4820 KB Output is correct
5 Correct 2 ms 4820 KB Output is correct
6 Correct 17 ms 4820 KB Output is correct
7 Correct 16 ms 4820 KB Output is correct
8 Correct 31 ms 4820 KB Output is correct
9 Correct 9 ms 4820 KB Output is correct
10 Correct 37 ms 4860 KB Output is correct
11 Correct 2 ms 4860 KB Output is correct
12 Correct 2 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 21 ms 4860 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 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 2 ms 4860 KB Output is correct
5 Correct 2 ms 4860 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 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 3 ms 4860 KB Output is correct
5 Correct 3 ms 4860 KB Output is correct
6 Correct 3 ms 4860 KB Output is correct
7 Correct 4 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

# 결과 실행 시간 메모리 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 3 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 13 ms 4860 KB Output is correct
12 Correct 14 ms 4860 KB Output is correct
13 Correct 43 ms 4860 KB Output is correct
14 Correct 12 ms 4860 KB Output is correct
15 Correct 66 ms 9388 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 9388 KB Output is correct
2 Correct 3 ms 9388 KB Output is correct
3 Correct 2 ms 9388 KB Output is correct

Subtask #8
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9388 KB Output is correct
2 Correct 2 ms 9388 KB Output is correct
3 Correct 2 ms 9388 KB Output is correct
4 Correct 2 ms 9388 KB Output is correct
5 Correct 2 ms 9388 KB Output is correct
6 Correct 2 ms 9388 KB Output is correct
7 Correct 2 ms 9388 KB Output is correct
8 Correct 2 ms 9388 KB Output is correct

Subtask #9
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9388 KB Output is correct
2 Correct 2 ms 9388 KB Output is correct
3 Correct 3 ms 9388 KB Output is correct
4 Correct 2 ms 9388 KB Output is correct
5 Correct 2 ms 9388 KB Output is correct
6 Correct 2 ms 9388 KB Output is correct
7 Correct 3 ms 9388 KB Output is correct
8 Correct 3 ms 9388 KB Output is correct
9 Correct 54 ms 9388 KB Output is correct
10 Correct 39 ms 9388 KB Output is correct
11 Correct 16 ms 9388 KB Output is correct
12 Correct 18 ms 9388 KB Output is correct
13 Incorrect 5 ms 9388 KB Output isn't correct

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9388 KB Output is correct
2 Correct 2 ms 9388 KB Output is correct
3 Correct 2 ms 9388 KB Output is correct
4 Correct 2 ms 9388 KB Output is correct
5 Correct 2 ms 9388 KB Output is correct
6 Correct 2 ms 9388 KB Output is correct
7 Correct 2 ms 9388 KB Output is correct
8 Correct 2 ms 9388 KB Output is correct
9 Correct 55 ms 9388 KB Output is correct
10 Correct 45 ms 9388 KB Output is correct
11 Correct 15 ms 9388 KB Output is correct
12 Correct 20 ms 9388 KB Output is correct
13 Incorrect 5 ms 9388 KB Output isn't correct
14 Halted 0 ms 0 KB -