oj.uz

Submission #913278

# Submission time Handle Problem Language Result Execution time Memory
913278 2024-01-20T07:07:11 Z 12345678 Gondola (IOI14_gondola) C++17
100 / 100
 93 ms 6108 KB 
#include "gondola.h"
#include <bits/stdc++.h>

using namespace std;

const int mod=1e9+9;
#define ll long long

int valid(int n, int inputSeq[])
{
    set<int> st;
    for (int i=0; i<n; i++) 
    {
        if (st.find(inputSeq[i])!=st.end()) return 0;
        st.insert(inputSeq[i]);
    }
    int s, cnt(0);
    bool can=1;
    pair<int, int> mn={INT_MAX, -1};
    for (int i=0; i<n; i++) mn=min(mn, {inputSeq[i], i});
    if (mn.first>n) return 1;
    cnt=mn.first;
    s=mn.second;
    for (int i=s; i<n; i++) if (inputSeq[i]!=cnt++&&inputSeq[i]<=n) can=0;
    for (int i=0; i<s; i++) if (inputSeq[i]!=cnt++&&inputSeq[i]<=n) can=0;
    return can;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    int cnt(0), res(0);
    set<pair<int, int>> s;
    for (int i=0; i<n; i++) if (gondolaSeq[i]>n) s.insert({gondolaSeq[i], i});
    pair<int, int> mn={INT_MAX, -1};
    for (int i=0; i<n; i++) if (gondolaSeq[i]<=n) mn=min(mn, {gondolaSeq[i], i});
    if (mn.first==INT_MAX) mn={1, 0};
    cnt=mn.first-1;
    vector<int> p(n);
    for (int i=mn.second; i<n; i++) p[i]=(++cnt)>n?cnt-n:cnt;
    for (int i=0; i<mn.second; i++) p[i]=(++cnt)>n?cnt-n:cnt;
    for (auto [x, y]:s)
    {
        replacementSeq[res++]=p[y];
        while (res+n!=x) replacementSeq[res]=res+n, res++;
    }
    return res;
}

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

ll binpow(ll x, ll a)
{
    if (a==0) return 1;
    if (a==1) return x;
    ll tmp=binpow(x, a/2);
    if (a%2==0) return (tmp*tmp)%mod;
    return (((tmp*tmp)%mod)*x)%mod;
}

int countReplacement(int n, int inputSeq[])
{
    if (!valid(n, inputSeq)) return 0;
    int sz(n+1);
    long long ans=1, l;
    set<pair<int, int>> s;
    for (int i=0; i<n; i++) if (inputSeq[i]>n) s.insert({inputSeq[i], i});
    if ((int)s.size()==n) for (int i=1; i<=n; i++) ans=n;
    l=(int)s.size();
    for (auto [x, y]:s)
    {
        ans=(ans*binpow(l, x-sz))%mod;
        sz=x+1;
        l--;
    }
    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 500 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 356 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 15 ms 2140 KB Output is correct
7 Correct 8 ms 604 KB Output is correct
8 Correct 22 ms 4028 KB Output is correct
9 Correct 6 ms 1372 KB Output is correct
10 Correct 28 ms 4692 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 500 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 10 ms 2136 KB Output is correct
7 Correct 8 ms 604 KB Output is correct
8 Correct 23 ms 3932 KB Output is correct
9 Correct 6 ms 1368 KB Output is correct
10 Correct 25 ms 4440 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 12 ms 2140 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 50 ms 4704 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.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 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 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 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 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 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 8 ms 856 KB Output is correct
12 Correct 7 ms 1116 KB Output is correct
13 Correct 16 ms 2516 KB Output is correct
14 Correct 8 ms 860 KB Output is correct
15 Correct 22 ms 2908 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 500 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 504 KB Output is correct
6 Correct 1 ms 356 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 46 ms 4444 KB Output is correct
10 Correct 32 ms 3928 KB Output is correct
11 Correct 14 ms 1624 KB Output is correct
12 Correct 16 ms 1880 KB Output is correct
13 Correct 5 ms 600 KB Output is correct

Subtask #10
10.0 / 10.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 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 55 ms 4432 KB Output is correct
10 Correct 39 ms 3904 KB Output is correct
11 Correct 12 ms 1624 KB Output is correct
12 Correct 21 ms 1992 KB Output is correct
13 Correct 4 ms 752 KB Output is correct
14 Correct 58 ms 5496 KB Output is correct
15 Correct 93 ms 6108 KB Output is correct
16 Correct 14 ms 1480 KB Output is correct
17 Correct 48 ms 4140 KB Output is correct
18 Correct 26 ms 2604 KB Output is correct