oj.uz

Submission #731273

# Submission time Handle Problem Language Result Execution time Memory
731273 2023-04-27T08:45:18 Z lucri Gondola (IOI14_gondola) C++17
100 / 100
 32 ms 5596 KB 
#include <stdio.h>
#include <assert.h>
#include <algorithm>
#include <unordered_set>
#include "gondola.h"
#define MOD 1000000009


int poz[100010];
std::unordered_set<int>e;
int valid(int n, int inputSeq[])
{
    for(int i=0;i<n;++i)
    {
        if(e.find(inputSeq[i])!=e.end())
            return 0;
        e.insert(inputSeq[i]);
        if(1<=inputSeq[i]&&inputSeq[i]<=n)
            poz[inputSeq[i]]=i+1;
    }
    int dif=-1;
    for(int i=1;i<=n;++i)
        if(poz[i])
        {
            int val;
            if(i<=poz[i])
                val=poz[i]-i;
            else
                val=poz[i]+n-i;
            if(dif==-1)
                dif=val;
            else if(dif!=val)
                return 0;
        }
    return 1;
}

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

int ago[100010];

int truevalue(int val,int n)
{
    while(val<=0)
        val+=n;
    return val;
}

int goodshift(int n,int gondolaSeq[])
{
    int ls=-1;
    for(int i=0;i<n;++i)
        if(1<=gondolaSeq[i]&&gondolaSeq[i]<=n)
        {
            if(gondolaSeq[i]<=i+1)
                ls=i+1-gondolaSeq[i];
            else
                ls=i+1+n-gondolaSeq[i];
            break;
        }
    if(ls==-1)
    {
        for(int i=0;i<n;++i)
            ago[i+1]=gondolaSeq[i];
        return 0;
    }
    for(int i=0;i<n;++i)
        ago[truevalue(i+1-ls,n)]=gondolaSeq[i];
    return 1;
}

int pozval[250010],valac;

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    goodshift(n,gondolaSeq);
    for(int i=1;i<=n;++i)
        pozval[ago[i]]=i;
    valac=n;
    for(int i=1;i<=n;++i)
        ago[i]=i;
    for(int i=n+1;i<=250000;++i)
    {
        if(pozval[i]!=0)
        {
            while(valac<i)
            {
                replacementSeq[valac-n]=ago[pozval[i]];
                ++valac;
                ago[pozval[i]]=valac;
            }
        }
    }
    return valac-n;
}

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

long long ans=1;

long long putere(long long a,long long b)
{
    if(b==0)
        return 1;
    long long m=putere(a,b/2);
    m*=m;
    m%=MOD;
    if(b%2)
    {
        m*=a;
        m%=MOD;
    }
    return m;
}

int countReplacement(int n, int inputSeq[])
{
    if(valid(n,inputSeq)==0)
        return 0;
    std::sort(inputSeq,inputSeq+n);
    if(inputSeq[0]>n)
        ans*=n;
    int poz=0;
    while(poz<n&&inputSeq[poz]<=n)
        ++poz;
    if(poz!=0)
        inputSeq[poz-1]=n;
    for(;poz<n;++poz)
    {
        if(poz==0)
            ans*=putere(n-poz,inputSeq[poz]-n-1);
        else
            ans*=putere(n-poz,inputSeq[poz]-inputSeq[poz-1]-1);
        ans%=MOD;
    }
    return ans;
}

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

Subtask #2
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
6 Correct 7 ms 2096 KB Output is correct
7 Correct 13 ms 928 KB Output is correct
8 Correct 12 ms 3684 KB Output is correct
9 Correct 5 ms 1516 KB Output is correct
10 Correct 13 ms 4124 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 1 ms 212 KB Output is correct
6 Correct 10 ms 2076 KB Output is correct
7 Correct 9 ms 980 KB Output is correct
8 Correct 11 ms 3720 KB Output is correct
9 Correct 4 ms 1620 KB Output is correct
10 Correct 15 ms 4196 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 11 ms 1992 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 22 ms 5596 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 1 ms 212 KB Output is correct
4 Correct 1 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 1 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 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 2 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #6
20.0 / 20.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 1 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 2 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 10 ms 1136 KB Output is correct
12 Correct 9 ms 1364 KB Output is correct
13 Correct 11 ms 1668 KB Output is correct
14 Correct 8 ms 1108 KB Output is correct
15 Correct 18 ms 2668 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #8
15.0 / 15.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 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 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #9
15.0 / 15.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 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 20 ms 3812 KB Output is correct
10 Correct 22 ms 3288 KB Output is correct
11 Correct 7 ms 1492 KB Output is correct
12 Correct 8 ms 1712 KB Output is correct
13 Correct 2 ms 596 KB Output is correct

Subtask #10
10.0 / 10.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 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 21 ms 3852 KB Output is correct
10 Correct 17 ms 3300 KB Output is correct
11 Correct 8 ms 1492 KB Output is correct
12 Correct 8 ms 1712 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 26 ms 3940 KB Output is correct
15 Correct 32 ms 5348 KB Output is correct
16 Correct 5 ms 1112 KB Output is correct
17 Correct 20 ms 3172 KB Output is correct
18 Correct 10 ms 1840 KB Output is correct