oj.uz

답안 #107784

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
107784 2019-04-25T19:16:00 Z FiloSanza 곤돌라 (IOI14_gondola) C++14
45 / 100
 51 ms 4856 KB 
#include <bits/stdc++.h>
#include "gondola.h"

using namespace std;

int valid(int N, int inputSeq[])
{
    vector<int> v, s;
    v.reserve(N);
    map<int, int> cont;
    for(int i=0; i<N; i++) 
        if(inputSeq[i] <= N)
            v.push_back(inputSeq[i]);
        else
            s.push_back(inputSeq[i]);

    for(auto i : v) cont[i]++;
    for(auto i : s) cont[i]++;
    for(auto i : cont) if(i.second > 1) return 0;

    if(v.empty()) return 1;

    int mini = min_element(v.begin(), v.end()) - v.begin();
    for(int i=mini+1; i!=mini; i=(i+1)%v.size()){
        if(i == 0 && v.back() >= v.front()) return 0;
        if(v[i] <= v[i-1]) return 0;
    }

    return 1;
}

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

int replacement(int N, int gondolaSeq[], int replacementSeq[])
{
    int cont = 0;
    vector<int> seq;
    vector<pair<int, int>> s;
    vector<int> v;

    for(int i=0; i<N; i++) 
        if(gondolaSeq[i] <= N)
            v.push_back(gondolaSeq[i]);

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

    if(!v.empty()){
        deque<int> q;
        for(int i=0; i<N; i++) q.push_back(gondolaSeq[i]);

        while(q.front() != v.front()){
            q.push_front(q.back());
            q.pop_back();
        }

        for(int i=1; i<v.front(); i++){
            q.push_front(q.back());
            q.pop_back();
        }
        
        while(!q.empty()){
            seq.push_back(q.front());
            q.pop_front();
        }
    }
    else{
        for(int i=0; i<N; i++) seq.push_back(gondolaSeq[i]);
    }
    
    for(int i=0; i<N; i++){
        if(seq[i] >= N)
            s.push_back({seq[i], i+1});
    }

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

    if(s.empty()) return 0;

    int nxt = N+1;
    for(auto i : s){
        int to = i.second;
        while(nxt <= i.first){
            replacementSeq[cont++] = to;
            to = nxt;
            nxt++;
        }
    }

    return cont;
}

//----------------------
const int MOD = 1e9+9;

int countReplacement(int N, int gondolaSeq[])
{
    if(valid(N, gondolaSeq) == 0) return 0;

    int cont = 0;
    vector<int> seq;
    vector<int> s;
    vector<int> v;

    for(int i=0; i<N; i++) 
        if(gondolaSeq[i] <= N)
            v.push_back(gondolaSeq[i]);

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

    if(!v.empty()){
        deque<int> q;
        for(int i=0; i<N; i++) q.push_back(gondolaSeq[i]);

        while(q.front() != v.front()){
            q.push_front(q.back());
            q.pop_back();
        }

        for(int i=1; i<v.front(); i++){
            q.push_front(q.back());
            q.pop_back();
        }
        
        while(!q.empty()){
            seq.push_back(q.front());
            q.pop_front();
        }
    }
    else{
        for(int i=0; i<N; i++) seq.push_back(gondolaSeq[i]);
    }    
    for(int i=0; i<N; i++){
        if(seq[i] >= N)
            s.push_back(seq[i]);
    }

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

    if(s.empty()) return 0;
    int curr = N+1, pos = 0;
    int ans = 1;
    while(curr < s.back()){
        if(curr == s[pos]){
            curr++;
            pos++;
            continue;
        }

        ans = (ans * (s.size() - pos)) % MOD;
        curr++;
    }    
    if(s.size() == N) ans = (ans * N) % MOD;
    return ans;
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:152:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(s.size() == N) ans = (ans * N) % MOD;
        ~~~~~~~~~^~~~
gondola.cpp:99:9: warning: unused variable 'cont' [-Wunused-variable]
     int cont = 0;
         ^~~~

Subtask #1
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 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct

Subtask #2
5.0 / 5.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 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 16 ms 2432 KB Output is correct
7 Correct 51 ms 4056 KB Output is correct
8 Correct 34 ms 4216 KB Output is correct
9 Correct 10 ms 1536 KB Output is correct
10 Correct 42 ms 4856 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 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 Correct 3 ms 384 KB Output is correct
6 Correct 17 ms 2432 KB Output is correct
7 Correct 47 ms 4088 KB Output is correct
8 Correct 28 ms 4188 KB Output is correct
9 Correct 10 ms 1536 KB Output is correct
10 Correct 40 ms 4856 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Incorrect 2 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 356 KB Output is correct
4 Correct 2 ms 384 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 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 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 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct

Subtask #6
20.0 / 20.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 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 16 ms 2040 KB Output is correct
12 Correct 17 ms 2296 KB Output is correct
13 Correct 19 ms 1340 KB Output is correct
14 Correct 15 ms 2040 KB Output is correct
15 Correct 23 ms 2424 KB Output is correct

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

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

Subtask #9
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

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