oj.uz

답안 #48758

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
48758 2018-05-18T14:48:42 Z doowey 곤돌라 (IOI14_gondola) C++14
55 / 100
 24 ms 4584 KB 
    #include <bits/stdc++.h>
    #include "gondola.h"
     
    using namespace std;
    typedef pair<int,int> pii;
     
    #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;
      bool ok = true;
      int start[n];
      for(int i = 0;i < n;i ++){
        if(gondolas[i] > n) 
          ok = false;
        if(gondolas[i] <= n)
          rx = i;
      }
      if(ok)
        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 ix;
      int ii = n + 1;
      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;
    }
     
    //----------------------
     
    int countReplacement(int n, int inputSeq[])
    {
      return -3;
    }

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1512 KB Output is correct
2 Correct 2 ms 1696 KB Output is correct
3 Correct 2 ms 1696 KB Output is correct
4 Correct 3 ms 1696 KB Output is correct
5 Correct 2 ms 1696 KB Output is correct
6 Correct 8 ms 1768 KB Output is correct
7 Correct 16 ms 1892 KB Output is correct
8 Correct 13 ms 2020 KB Output is correct
9 Correct 6 ms 2020 KB Output is correct
10 Correct 14 ms 2148 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4584 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4584 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4584 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4584 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -