Submission #578971

#	Time	Username	Problem	Language	Result	Execution time	Memory
578971		tranxuanbach	Gondola (IOI14_gondola)	C++17	100 / 100	40 ms	2384 KiB

gondola

#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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 5 / 5
• Subtask 8: 15 / 15
• Subtask 9: 15 / 15
• Subtask 10: 10 / 10