Submission #969549

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
969549	2024-04-25T09:52:06 Z	GrindMachine	Gondola (IOI14_gondola)	C++17	90 / 100	99 ms	262144 KB

gondola

#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;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 9;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "gondola.h"

int valid(int n, int a[])
{
    rep(i,n) a[i]--;
    
    set<int> st;
    rep(i,n){
        if(st.count(a[i])){
            return 0;
        }
        st.insert(a[i]);
    }

    int val = -1;
    rep(i,n){
        if(val != -1){
            val = (val+1)%n;
        }

        if(a[i] >= n) conts;

        if(val == -1){
            val = a[i];
        }
        else{
            if(a[i] != val){
                return 0;
            }
        }
    }

    return 1;
}

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

int replacement(int n, int a[], int ans[])
{
    rep(i,n) a[i]--;
    int m = *max_element(a,a+n);
    int b[n];
    rep(i,n) b[i] = a[i];

    rep(i,n){
        if(a[i] < n){
            b[a[i]] = a[i];
            int ptr = (a[i]+1)%n;

            for(int j = (i+1)%n; j != i; j = (j+1)%n){
                b[ptr] = a[j];
                ptr = (ptr+1)%n;
            }

            break;
        }
    }

    rep(i,n) a[i] = b[i];

    vector<int> pos(m+5,-1);
    rep(i,n) pos[a[i]] = i;

    rep(i,n) b[i] = i;
    set<int> st;
    rep(i,n){
        if(b[i] != a[i]){
            st.insert(i);
        }
    }

    int siz = 0;

    for(int x = n; x <= m; ++x){
        if(pos[x] != -1){
            int i = pos[x];
            assert(st.count(i));
            st.erase(i);
            ans[siz++] = b[i];
            b[i] = x;
        }
        else{
            assert(!st.empty());
            int i = *st.begin();
            ans[siz++] = b[i];
            b[i] = x;
        }
    }

    rep(i,n) assert(a[i] == b[i]);

    rep(i,siz) ans[i]++;
    return siz;
}

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


ll bexp(ll a, ll b) {
    if (a == 0) return 1;

    ll res = 1;

    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }

    return res;
}

int countReplacement(int n, int a[])
{
    if(!valid(n,a)){
        return 0;
    }

    int m = *max_element(a,a+n);
    int b[n];
    rep(i,n) b[i] = a[i];

    rep(i,n){
        if(a[i] < n){
            b[a[i]] = a[i];
            int ptr = (a[i]+1)%n;

            for(int j = (i+1)%n; j != i; j = (j+1)%n){
                b[ptr] = a[j];
                ptr = (ptr+1)%n;
            }

            break;
        }
    }

    rep(i,n) a[i] = b[i];

    vector<int> pos(m+5,-1);
    rep(i,n) pos[a[i]] = i;

    set<int> st;
    rep(i,n){
        if(a[i] != i){
            st.insert(i);
        }
    }

    set<int> there;
    rep(i,n){
        if(a[i] >= n){
            there.insert(a[i]);
        }
    }

    vector<int> c(all(there));
    ll ans = 1;

    if(!c.empty()){
        ans = bexp(sz(c),c[0]-n);
    }

    ll siz = sz(c);

    rep(i,sz(c)-1){
        siz--;
        ans = ans*bexp(siz,c[i+1]-c[i]-1)%MOD;
    }

    bool all_big = true;
    rep(i,n){
        if(a[i] < n){
            all_big = false;
        }
    }

    if(all_big){
        ans = ans*n%MOD;
    }

    return ans;
}

Subtask #1
5.0 / 5.0

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

#	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	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	10 ms	2268 KB	Output is correct
7	Correct	7 ms	604 KB	Output is correct
8	Correct	21 ms	4332 KB	Output is correct
9	Correct	6 ms	1624 KB	Output is correct
10	Correct	25 ms	4428 KB	Output is correct

Subtask #3
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	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	10 ms	2140 KB	Output is correct
7	Correct	6 ms	652 KB	Output is correct
8	Correct	20 ms	3932 KB	Output is correct
9	Correct	6 ms	1372 KB	Output is correct
10	Correct	24 ms	4556 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	12 ms	2012 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	31 ms	4772 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	544 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct

Subtask #5
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	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	344 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	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	1 ms	348 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	344 KB	Output is correct
11	Correct	7 ms	1372 KB	Output is correct
12	Correct	8 ms	1372 KB	Output is correct
13	Correct	20 ms	2748 KB	Output is correct
14	Correct	7 ms	1116 KB	Output is correct
15	Correct	21 ms	2944 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.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	344 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	344 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	52 ms	7272 KB	Output is correct
10	Correct	37 ms	5464 KB	Output is correct
11	Correct	15 ms	3672 KB	Output is correct
12	Correct	18 ms	3676 KB	Output is correct
13	Correct	4 ms	1884 KB	Output is correct

Subtask #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	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	50 ms	7252 KB	Output is correct
10	Correct	37 ms	5468 KB	Output is correct
11	Correct	15 ms	3676 KB	Output is correct
12	Correct	18 ms	3744 KB	Output is correct
13	Correct	4 ms	1884 KB	Output is correct
14	Runtime error	99 ms	262144 KB	Execution killed with signal 9
15	Halted	0 ms	0 KB	-

Submission #969549

Compilation message