oj.uz

답안 #103755

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
103755 2019-04-02T12:49:45 Z SecretAgent007 곤돌라 (IOI14_gondola) C++17
60 / 100
 95 ms 10104 KB 
#include "gondola.h"
#include <bits/stdc++.h>

using namespace std;

int valid(int n, int inputSeq[]){

    int index = 0;
    int num = n;

    map< int, bool> visited;

    for(int i = 0; i < n; i++){
        if(visited[inputSeq[i]]) return 0;
        visited[inputSeq[i]] = true;
        if(inputSeq[i] <= num){
            num = inputSeq[i];
            index = i;
        }
    }

    int start = (index-num+1+n)%n;

    int curr = 1;

    for(int i = start; i < n; i++){
        if(inputSeq[i] <= n && inputSeq[i] != curr) return 0;
        curr++;
    }
    for(int j = 0; j < start; j++){
        if(inputSeq[j] <= n && inputSeq[j] != curr) return 0;
        curr++;
    }
    return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[]){
    int index = 0;
    int num = n;

    int maxi = 0;

    for(int i = 0; i < n; i++){
        if(gondolaSeq[i] <= num){
            num = gondolaSeq[i];
            index = i;
        }
        maxi = max(maxi, gondolaSeq[i]);
    }

    int start = (index-num+1+n)%n;

    if(gondolaSeq[index] > n) start = 0;

    int curr = 1;

    map<int, int> mape;

    vector< int > current(n+1);

    for(int i = 1; i <= n; i++){
        current[i] = i;
    }

    int in;

    for(int i = start; i < n; i++){
        mape[gondolaSeq[i]] = curr;
        if(gondolaSeq[i] == maxi) in = curr;
        curr++;
    }
    for(int j = 0; j < start; j++){
        mape[gondolaSeq[j]] = curr;
        if(gondolaSeq[j] == maxi) in = curr;
        curr++;
    }

    int c = 0;

    for(int i = n+1; i <= maxi; i++){
        if(mape[i] != 0){
            replacementSeq[c] = current[mape[i]];
            current[mape[i]] = i;
        }else{
            replacementSeq[c] = current[in];
            current[in] = i;
        }
        c++;
    }

    return c;
}

int last;

vector< int > memo;
map<int, bool> visited;
vector< int > ve;
vector< int > cnt;

const int mod = 1e9+9;

int dp(int curr, int n){
    if(curr >= last){
        return 1;
    }
    if(memo[curr] != -1) return memo[curr];

    memo[curr] = 0;

    if(visited[curr]){
        return memo[curr] = dp(curr+1,n);
    }

    int index = lower_bound(cnt.begin(), cnt.end(), curr)-cnt.begin();
    int nb = n-index-1+cnt[index]-curr;
    nb = nb%mod;

   // cout << curr << ' ' << nb << endl;
    /*
    for(int i = 0; i < n; i++){
        if(ve[i] > curr){
            memo[curr] += dp(curr+1,n);
            memo[curr] %= mod;
        }
    }
*/
    return memo[curr] = (nb*dp(curr+1,n))%mod;
}

int countReplacement(int n, int inputSeq[]){
    if(!valid(n,inputSeq)) return 0;

    ve.resize(n);
    cnt.resize(n);

    for(int i = 0; i < n; i++){
        last = max(last, inputSeq[i]);
        ve[i] = inputSeq[i];
        cnt[i] = inputSeq[i];
        visited[inputSeq[i]] = true;
    }

    sort(cnt.begin(), cnt.end());

    memo.resize(last+1,-1);

    return dp(n+1, n);
}
/*
int main(){
    int n;
    cin >> n;
    int v[n];
    int maxi = 0;
    for(int i = 0; i < n; i++){
        cin >> v[i];
        maxi = max(maxi, v[i]);
    }
    int ans[maxi-n];
    cout << replacement(n,v,ans) << endl;
    for(int a : ans){
        cout << a << ' ';
    }
    cout << endl;

    cout << "NUMBER " << countReplacement(n,v) << endl;
}

*/

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:85:43: warning: 'in' may be used uninitialized in this function [-Wmaybe-uninitialized]
             replacementSeq[c] = current[in];
                                           ^

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 23 ms 2296 KB Output is correct
7 Correct 14 ms 768 KB Output is correct
8 Correct 32 ms 3960 KB Output is correct
9 Correct 12 ms 1476 KB Output is correct
10 Correct 42 ms 4472 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 304 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 21 ms 2196 KB Output is correct
7 Correct 13 ms 768 KB Output is correct
8 Correct 30 ms 3968 KB Output is correct
9 Correct 10 ms 1536 KB Output is correct
10 Correct 50 ms 4600 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 26 ms 2048 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 71 ms 4692 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 3 ms 484 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 31 ms 4600 KB Output is correct
12 Correct 39 ms 5240 KB Output is correct
13 Correct 65 ms 4708 KB Output is correct
14 Correct 31 ms 4600 KB Output is correct
15 Correct 95 ms 10104 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Incorrect 3 ms 256 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 356 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Incorrect 3 ms 256 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 444 KB Output is correct
5 Incorrect 2 ms 256 KB Output isn't correct
6 Halted 0 ms 0 KB -