oj.uz

Submission #578971

# Submission time Handle Problem Language Result Execution time Memory
578971 2022-06-18T08:58:45 Z tranxuanbach Gondola (IOI14_gondola) C++17
100 / 100
 40 ms 2384 KB 
#ifndef FEXT

#include "gondola.h"

#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

int valid(int n, int a[]){
    {
        vi b(a, a + n);
        sort(bend(b)); b.erase(unique(bend(b)), b.end());
        if (isz(b) != n){
            return 0;
        }
    }
    int smallpos = min_element(a, a + n) - a;
    int i = smallpos, x = a[i];
    do{
        if (a[i] <= n and a[i] != x){
            return 0;
        }
        i = (i + 1) % n; x++;
    } while (i != smallpos);
    return 1;
}

int replacement(int n, int a[], int b[]){
    int smallpos = min_element(a, a + n) - a, largepos = max_element(a, a + n) - a;
    int mx = a[largepos];
    int i = smallpos, x = a[i];
    i = (i - (x - 1) % n + n) % n; x = 1;
    int pos1 = i;
    int posmx = (largepos - pos1 + n) % n + 1;
    For(i, 0, mx - n){
        b[i] = (i == 0 ? posmx : n + i);
    }
    vpii changepos;
    do{
        if (a[i] > n and a[i] != mx){
            changepos.emplace_back(a[i], x);
        }
        i = (i + 1) % n; x++;
    } while (i != pos1);
    sort(bend(changepos));
    Fora(elem, changepos){
        b[elem.fi - n] = b[elem.fi - n - 1];
        b[elem.fi - n - 1] = elem.se;
    }
    return mx - n;
}

int binpow(int x, int y, int mod){
    int ans = 1;
    while (y){
        if (y & 1){
            ans = (ll)ans * x % mod;
        }
        x = (ll)x * x % mod;
        y >>= 1;
    }
    return ans;
}

int countReplacement(int n, int a[]){
    {
        vi b(a, a + n);
        sort(bend(b)); b.erase(unique(bend(b)), b.end());
        if (isz(b) != n){
            return 0;
        }
    }
    int smallpos = min_element(a, a + n) - a;
    int i = smallpos, x = a[i];
    do{
        if (a[i] <= n and a[i] != x){
            return 0;
        }
        i = (i + 1) % n; x++;
    } while (i != smallpos);

    const int mod = 1e9 + 9;

    vi b = {n};
    For(i, 0, n){
        if (a[i] > n){
            b.emplace_back(a[i]);
        }
    }
    sort(bend(b), greater <>());
    int ans = 1;
    For(i, 0, isz(b) - 1){
        ans = (ll)ans * binpow(i + 1, b[i] - b[i + 1] - 1, mod) % mod;
    }
    if (isz(b) == n + 1){
        ans = (ll)ans * n % mod;
    }
    return ans;
}

#ifdef FEXT

int gondolaSequence[100001];
int replacementSequence[250001];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    freopen("KEK.inp", "r", stdin);
    freopen("KEK.out", "w", stdout);
    int i, n, tag;
    int nr; 
    assert(scanf("%d", &tag)==1);
    assert(scanf("%d", &n)==1);
    for(i=0;i< n;i++)
    assert( scanf("%d", &gondolaSequence[i]) ==1);

    switch (tag){
    case 1: case 2: case 3:
    printf("%d\n", valid(n, gondolaSequence));
    break;

    case 4: case 5: case 6:
    nr = replacement(n, gondolaSequence, replacementSequence);
    printf("%d ", nr);
    if (nr > 0)
    {
    for (i=0; i<nr-1; i++)
    printf("%d ", replacementSequence[i]);
    printf("%d\n", replacementSequence[nr-1]);
    }  
    else printf("\n");
    break;

    case 7: case 8: case 9: case 10:
    printf("%d\n",  countReplacement(n, gondolaSequence));  
    break;
    }

    return 0;
}

#endif

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 6 ms 596 KB Output is correct
7 Correct 14 ms 948 KB Output is correct
8 Correct 9 ms 852 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 13 ms 852 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 6 ms 596 KB Output is correct
7 Correct 14 ms 980 KB Output is correct
8 Correct 9 ms 852 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 14 ms 980 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 5 ms 468 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 13 ms 980 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 356 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 7 ms 612 KB Output is correct
12 Correct 9 ms 596 KB Output is correct
13 Correct 13 ms 1244 KB Output is correct
14 Correct 7 ms 496 KB Output is correct
15 Correct 19 ms 2180 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 308 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 19 ms 1472 KB Output is correct
10 Correct 14 ms 1356 KB Output is correct
11 Correct 6 ms 724 KB Output is correct
12 Correct 9 ms 812 KB Output is correct
13 Correct 2 ms 340 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 17 ms 1472 KB Output is correct
10 Correct 14 ms 1252 KB Output is correct
11 Correct 6 ms 768 KB Output is correct
12 Correct 7 ms 832 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 26 ms 2288 KB Output is correct
15 Correct 40 ms 2384 KB Output is correct
16 Correct 5 ms 724 KB Output is correct
17 Correct 24 ms 1624 KB Output is correct
18 Correct 10 ms 1200 KB Output is correct