oj.uz

답안 #48777

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
48777 2018-05-18T17:35:32 Z doowey 곤돌라 (IOI14_gondola) C++14
90 / 100
 27 ms 3372 KB 
#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,ll k){
  if(k == 0)
    return 1LL;
  ll ans = powr(n,k/2);
  ans = (ans * ans) % MOD;
  if(k & 1)
    ans = (ans * n) % MOD;
  return ans;
}

int countReplacement(int n, int seq[])
{
  if(!valid(n,seq)){
    return 0;
  }
  int tk = 1000000009;
  for(int i = 0;i < n;i ++){
    tk = min(tk,seq[i]);
  }
  ll ans = 1;
  if(tk > n)
    ans = n;
  vector<ll>R;
  for(int i = 0;i < n;i ++){
    if(seq[i] > n)
      R.push_back((ll)seq[i]);
  }
  R.push_back(n);
  sort(R.begin(),R.end());
  ll ff = (ll)R.size();
  ff--;
  for(int i = 1;i < R.size(); i ++){
    ans *= powr(ff,R[i] - R[i - 1] - 1);
    ans %= MOD;
    --ff;
  }
  return ans;
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:162:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1;i < R.size(); i ++){
                 ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1492 KB Output is correct
2 Correct 3 ms 1492 KB Output is correct
3 Correct 3 ms 1584 KB Output is correct
4 Correct 3 ms 1584 KB Output is correct
5 Correct 2 ms 1584 KB Output is correct
6 Correct 8 ms 1772 KB Output is correct
7 Correct 17 ms 1900 KB Output is correct
8 Correct 22 ms 2028 KB Output is correct
9 Correct 9 ms 2028 KB Output is correct
10 Correct 27 ms 2156 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

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

Subtask #10
0 / 10.0

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