oj.uz

Submission #1002594

# Submission time Handle Problem Language Result Execution time Memory
1002594 2024-06-19T16:39:16 Z codexistent Gondola (IOI14_gondola) C++14
75 / 100
 38 ms 3832 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){
        FOR(i, 1, n) r = (r * (ll)(i)) % MOD;
    }
    return r;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory 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 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory 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 440 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 7 ms 1280 KB Output is correct
8 Correct 5 ms 1092 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 7 ms 1116 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory 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 568 KB Output is correct
7 Correct 6 ms 1368 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 1192 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 6 ms 1156 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 444 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 444 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 444 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 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 444 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 7 ms 1112 KB Output is correct
12 Correct 7 ms 1116 KB Output is correct
13 Correct 15 ms 2756 KB Output is correct
14 Correct 5 ms 1116 KB Output is correct
15 Correct 15 ms 3152 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 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 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 436 KB Output is correct

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 444 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 448 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 33 ms 3672 KB Output is correct
10 Correct 27 ms 2908 KB Output is correct
11 Correct 14 ms 1628 KB Output is correct
12 Correct 15 ms 1884 KB Output is correct
13 Incorrect 5 ms 604 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory 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 344 KB Output is correct
5 Correct 0 ms 440 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
9 Correct 38 ms 3832 KB Output is correct
10 Correct 28 ms 2908 KB Output is correct
11 Correct 13 ms 1628 KB Output is correct
12 Correct 16 ms 1840 KB Output is correct
13 Incorrect 5 ms 760 KB Output isn't correct
14 Halted 0 ms 0 KB -