답안 #48768 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48768	2018-05-18T17:16:29 Z	doowey	곤돌라 (IOI14_gondola)	C++14	90 / 100	32 ms	3428 KB

gondola

#include <bits/stdc++.h>
#include "gondola.h"

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;

#define fi first
#define se second
#define mp make_pair

const int N = (int)25e4 + 1293;

int valid(int n, int inputSeq[])
{
  int cnt[N];
  for(int j = 0;j < N;j ++ )
    cnt[j] = 0;
  int rest[n];
  int maz = (int)4e5 + 12345;
  for(int i = 0; i < n;i ++){
    cnt[inputSeq[i]]++;
    if(cnt[inputSeq[i]] >= 2)
      return 0;
    maz = min(maz, inputSeq[i]);
    rest[i] = inputSeq[i];
  }
  if(maz > n)
    return 1;
  int p,j;
  for(int i = 0;i < n;i ++ ){
    if(rest[i] <= n){
      p = rest[i]+1;
      j = i+1;
      j %= N;
      while(p <= n){
        rest[j] = p;
        p++;
        j++;
        j%=n;
      }
      p = 1;
      while(p < rest[i]){
        rest[j] = p;
        j++;
        j %= n;
        p++;
      }
      break;
    }
  }
  for(int i = 0; i < n;i ++){
    if(inputSeq[i] <= n){
      if(rest[i] != inputSeq[i])
        return 0;
    }
  }
  return 1;
}

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

int replacement(int n, int gondolas[], int replacementSeq[])
{
  int rx = 0;
  int start[n];
  bool is = false;
  for(int i = 0;i < n;i ++){
    if(gondolas[i] > n)
      is = true;
    if(gondolas[i] <= n)
      rx = i;
  }
  if(is == false)
    return 0;
  int ini;
  if(gondolas[rx] > n)
    start[rx] = 1;
  else
    start[rx] = gondolas[rx];
  int p = start[rx] + 1;
  ini = start[rx];
  rx ++ ;
  while(p <= n){
    rx %= n;
    start[rx] = p;
    rx++;
    p++;
  }
  p = 1;
  rx %= n;
  while(p < ini){
    start[rx] = p;
    p++;
    rx++;
    rx %= n;
  }
  vector<pii>qq;
  for(int i = 0;i < n;i ++){
    if(start[i] < gondolas[i]){
      qq.push_back(mp(gondolas[i],i));
    }
  }
  sort(qq.begin(),qq.end());
  int mak;
  int ii = n + 1;
  int ix;
  int sz = 0;
  for(auto x : qq){
    mak = x.fi;
    ix = x.se;
    replacementSeq[sz] = start[ix];
    sz++;
    start[ix] = ii;
    ii++;
    while(start[ix] < mak){
      replacementSeq[sz] = start[ix];
      start[ix] = ii;
      sz++;
      ii++;
    }
    ii = mak + 1;
  }
  return sz;
}

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

const ll MOD = (int)1e9 + 9;

ll powr(ll n,int k){
  if(k == 0)
    return 1LL;
  ll hf = powr(n,k/2);
  hf = (1LL * hf * hf) % MOD;
  if(k&1)
    hf = (1LL * hf * n) % MOD;
  return hf;
}

int countReplacement(int n, int inputSeq[])
{
  if(!valid(n,inputSeq)){
    return 0;
  }
  ll ans = 1;
  int mn = (int)1e9 + 999;
  for(int i = 0;i < n;i ++)
    mn = min(mn,inputSeq[i]);
  if(mn > n)
    ans = n; // n cylcic rotations
  vector<int>nex;
  nex.push_back(n);
  for(int i = 0;i < n;i ++)
    if(inputSeq[i] > n)
      nex.push_back(inputSeq[i]);
  sort(nex.begin(),nex.end());
  ll tk = (ll)nex.size() - 1;
  for(int i = 1;i < (int)nex.size(); i ++){
    ans = (1LL * ans * powr(tk,nex[i] - nex[i - 1] - 1)) % MOD;
    --tk;
  }
  return ans;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1272 KB	Output is correct
2	Correct	3 ms	1384 KB	Output is correct
3	Correct	3 ms	1436 KB	Output is correct
4	Correct	2 ms	1608 KB	Output is correct
5	Correct	3 ms	1608 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1608 KB	Output is correct
2	Correct	3 ms	1608 KB	Output is correct
3	Correct	3 ms	1608 KB	Output is correct
4	Correct	3 ms	1608 KB	Output is correct
5	Correct	3 ms	1608 KB	Output is correct
6	Correct	8 ms	1948 KB	Output is correct
7	Correct	14 ms	1948 KB	Output is correct
8	Correct	13 ms	2044 KB	Output is correct
9	Correct	6 ms	2044 KB	Output is correct
10	Correct	17 ms	2172 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2172 KB	Output is correct
2	Correct	3 ms	2172 KB	Output is correct
3	Correct	3 ms	2172 KB	Output is correct
4	Correct	3 ms	2172 KB	Output is correct
5	Correct	8 ms	2172 KB	Output is correct
6	Correct	9 ms	2172 KB	Output is correct
7	Correct	17 ms	2172 KB	Output is correct
8	Correct	15 ms	2172 KB	Output is correct
9	Correct	7 ms	2172 KB	Output is correct
10	Correct	17 ms	2256 KB	Output is correct
11	Correct	3 ms	2256 KB	Output is correct
12	Correct	3 ms	2256 KB	Output is correct
13	Correct	10 ms	2256 KB	Output is correct
14	Correct	6 ms	2256 KB	Output is correct
15	Correct	17 ms	2256 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2256 KB	Output is correct
2	Correct	2 ms	2256 KB	Output is correct
3	Correct	2 ms	2256 KB	Output is correct
4	Correct	2 ms	2256 KB	Output is correct
5	Correct	2 ms	2256 KB	Output is correct
6	Correct	2 ms	2256 KB	Output is correct
7	Correct	2 ms	2256 KB	Output is correct
8	Correct	3 ms	2256 KB	Output is correct
9	Correct	3 ms	2256 KB	Output is correct
10	Correct	2 ms	2256 KB	Output is correct
11	Correct	13 ms	2256 KB	Output is correct
12	Correct	14 ms	2256 KB	Output is correct
13	Correct	19 ms	2256 KB	Output is correct
14	Correct	15 ms	2256 KB	Output is correct
15	Correct	24 ms	2600 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2600 KB	Output is correct
2	Correct	3 ms	2600 KB	Output is correct
3	Correct	3 ms	2600 KB	Output is correct
4	Correct	4 ms	2600 KB	Output is correct
5	Correct	4 ms	2600 KB	Output is correct
6	Correct	3 ms	2600 KB	Output is correct
7	Correct	3 ms	2600 KB	Output is correct
8	Correct	3 ms	2600 KB	Output is correct
9	Correct	32 ms	2604 KB	Output is correct
10	Correct	20 ms	2604 KB	Output is correct
11	Correct	10 ms	2604 KB	Output is correct
12	Correct	11 ms	2604 KB	Output is correct
13	Correct	5 ms	2604 KB	Output is correct

Subtask #10
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2604 KB	Output is correct
2	Correct	4 ms	2604 KB	Output is correct
3	Correct	3 ms	2604 KB	Output is correct
4	Correct	3 ms	2604 KB	Output is correct
5	Correct	4 ms	2604 KB	Output is correct
6	Correct	3 ms	2604 KB	Output is correct
7	Correct	3 ms	2604 KB	Output is correct
8	Correct	3 ms	2604 KB	Output is correct
9	Correct	31 ms	2604 KB	Output is correct
10	Correct	25 ms	2604 KB	Output is correct
11	Correct	9 ms	2604 KB	Output is correct
12	Correct	13 ms	2604 KB	Output is correct
13	Correct	5 ms	2604 KB	Output is correct
14	Runtime error	23 ms	3428 KB	Execution killed with signal 7 (could be triggered by violating memory limits)
15	Halted	0 ms	0 KB	-

답안 #48768

Compilation message