oj.uz

답안 #1002627

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1002627 2024-06-19T17:11:21 Z codexistent 곤돌라 (IOI14_gondola) C++14
90 / 100
 1000 ms 5248 KB 
#include <bits/stdc++.h>
#include <gondola.h>
using namespace std;
#define MOD 1000000009
#define ll long long
#define FOR(i, a, b) for(int i = a; i <= b; i++)
 
int diff(int n, int a, int b){
    if(b >= a) return b - a;
    else return (n - a) + b;
}
 
int valid(int n, int inputSeq[]){
    pair<int, int> prev = make_pair(-1, 0);
    set<int> s;
    FOR(i, 0, n - 1){
        if(inputSeq[i] <= n){
            if(prev.first == -1){
                prev = make_pair(i, inputSeq[i]);
            }else{
                if((((prev.second + diff(n, prev.first, i)) % n) == 0 ? n : ((prev.second + diff(n, prev.first, i)) % n)) != inputSeq[i]) return 0;
                prev = make_pair(i, inputSeq[i]);
            }
        }else{
            if(s.find(inputSeq[i]) != s.end()) return 0;
            s.insert(inputSeq[i]);
        }
    }
 
    return 1;
}
 
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
    int idx = -1, mx = -1;
    vector<pair<int, int> > v;
    FOR(i, 0, n - 1){
        if(gondolaSeq[i] <= n){
            idx = gondolaSeq[i] - i;
            if(idx <= 0) idx += n;
        }else{
            v.push_back(make_pair(gondolaSeq[i], i));
        }
        mx = max(mx, gondolaSeq[i]);
    }
    sort(v.begin(), v.end());
 
    if(idx == -1) idx = 1;
 
    set<int> s;
    FOR(i, 0, (int)(v.size() - 2)) {
        s.insert(v[i].first);
        replacementSeq[v[i].first - n - 1] = ((idx + v[i].second) % n == 0) ? n : ((idx + v[i].second) % n);
    }
 
    if(v.size()){
        int prev = ((idx + v[v.size() - 1].second) % n == 0) ? n : ((idx + v[v.size() - 1].second) % n);
        FOR(i, n + 1, mx) {
            if(s.find(i) == s.end()) {
                replacementSeq[i - (n + 1)] = prev;
                prev = i;
            }
        }
    }
    return mx - n;
}
 
int countReplacement(int n, int inputSeq[]){
    if(!valid(n, inputSeq)) return 0;
    ll r = 1;
    int c = 0, mx = -1;
    set<int> s;
    bool fct = true;
    FOR(i, 0, n - 1){
        if(inputSeq[i] <= n) fct = false;
        else{
            c++, s.insert(inputSeq[i]);
        }
        mx = max(mx, inputSeq[i]);
    }
 
    int c2 = 0;
    FOR(i, n + 1, mx){
        if(s.find(i) == s.end()){
            r = (r * (ll)(c - c2)) % MOD;
        }else{
            c2++;
        }
    }
    if(fct){
        r = (r * (ll)(n)) % MOD;
    }
    return r;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 4 ms 708 KB Output is correct
7 Correct 6 ms 1200 KB Output is correct
8 Correct 5 ms 1116 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 5 ms 1208 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 6 ms 1116 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 440 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 444 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 10 ms 1112 KB Output is correct
12 Correct 7 ms 1116 KB Output is correct
13 Correct 15 ms 2796 KB Output is correct
14 Correct 5 ms 1112 KB Output is correct
15 Correct 17 ms 3156 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 42 ms 3868 KB Output is correct
10 Correct 28 ms 2908 KB Output is correct
11 Correct 14 ms 1628 KB Output is correct
12 Correct 16 ms 1768 KB Output is correct
13 Correct 5 ms 604 KB Output is correct

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 37 ms 3676 KB Output is correct
10 Correct 27 ms 2908 KB Output is correct
11 Correct 13 ms 1624 KB Output is correct
12 Correct 15 ms 1972 KB Output is correct
13 Correct 5 ms 604 KB Output is correct
14 Execution timed out 1097 ms 5248 KB Time limit exceeded
15 Halted 0 ms 0 KB -