답안 #54598 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54598	2018-07-04T07:43:05 Z	win11905	곤돌라 (IOI14_gondola)	C++11	100 / 100	78 ms	9388 KB

gondola

#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);
  bool st = true;
  for(int i = 0; i < n; ++i) 
    if(inputSeq[i] > n) V.emplace_back(inputSeq[i]);
    else st = false;
  long ans = st ? n : 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	356 KB	Output is correct
3	Correct	2 ms	392 KB	Output is correct
4	Correct	2 ms	408 KB	Output is correct
5	Correct	2 ms	528 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	528 KB	Output is correct
2	Correct	2 ms	528 KB	Output is correct
3	Correct	2 ms	528 KB	Output is correct
4	Correct	2 ms	528 KB	Output is correct
5	Correct	2 ms	528 KB	Output is correct
6	Correct	21 ms	2404 KB	Output is correct
7	Correct	40 ms	2404 KB	Output is correct
8	Correct	27 ms	4124 KB	Output is correct
9	Correct	11 ms	4124 KB	Output is correct
10	Correct	34 ms	4844 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4844 KB	Output is correct
2	Correct	2 ms	4844 KB	Output is correct
3	Correct	2 ms	4844 KB	Output is correct
4	Correct	2 ms	4844 KB	Output is correct
5	Correct	2 ms	4844 KB	Output is correct
6	Correct	15 ms	4844 KB	Output is correct
7	Correct	13 ms	4844 KB	Output is correct
8	Correct	28 ms	4844 KB	Output is correct
9	Correct	10 ms	4844 KB	Output is correct
10	Correct	36 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	14 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	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

#	결과	실행 시간	메모리	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

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

Subtask #7
5.0 / 5.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

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	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	3 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
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	3 ms	9388 KB	Output is correct
9	Correct	52 ms	9388 KB	Output is correct
10	Correct	67 ms	9388 KB	Output is correct
11	Correct	18 ms	9388 KB	Output is correct
12	Correct	23 ms	9388 KB	Output is correct
13	Correct	5 ms	9388 KB	Output is correct

Subtask #10
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	48 ms	9388 KB	Output is correct
10	Correct	40 ms	9388 KB	Output is correct
11	Correct	17 ms	9388 KB	Output is correct
12	Correct	20 ms	9388 KB	Output is correct
13	Correct	5 ms	9388 KB	Output is correct
14	Correct	66 ms	9388 KB	Output is correct
15	Correct	78 ms	9388 KB	Output is correct
16	Correct	13 ms	9388 KB	Output is correct
17	Correct	46 ms	9388 KB	Output is correct
18	Correct	30 ms	9388 KB	Output is correct

답안 #54598

Compilation message