oj.uz

답안 #1017754

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1017754 2024-07-09T09:57:42 Z vivkostov 곤돌라 (IOI14_gondola) C++14
100 / 100
 54 ms 124776 KB 
#include<bits/stdc++.h>
#define endl '\n'
#include "gondola.h"
using namespace std;
const long long int maxn=1000000009;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
struct cell
{
    int v,st;
};
bool cmp(cell a1,cell a2)
{
    return a1.st<a2.st;
}
int n,a[200005],ind[200005],se[200005];
cell c[200005];
vector<bool>used(1000000009);
int valid(int n,int seq[])
{
    int br=0;
    for(int i=1; i<=n; i++)
    {
        a[i]=seq[i-1];
    }
    for(int i=1; i<=n; i++)
    {
        if(a[i]<=n)
        {
            if(!br)br=a[i];
            else
            {
                if(a[i]!=br)
                {
                    return 0;
                }
            }
        }
        if(used[a[i]])
        {
            return 0;
        }
        used[a[i]]=1;
        if(br)br++;
        if(br>n)br=1;
    }
    for(int i=n+2; i<=250000; i++)
    {
        if(used[i]&&!used[i-1])
        {
            return 0;
        }
    }
    return 1;
}
int replacement(int n, int seq[], int rseq[])
{
    int st=1,val=1,next=n+1;
    for(int i=1; i<=n; i++)
    {
        a[i]=seq[i-1];
    }
    for(int i=1; i<=n; i++)
    {
        if(a[i]<=n)
        {
            st=i;
            val=a[i];
            break;
        }
    }
    for(int i=st; i<=n; i++)
    {
        ind[i]=val;
        val++;
        if(val>n)val=1;
    }
    for(int i=1; i<st; i++)
    {
        ind[i]=val;
        val++;
    }
    for(int i=1; i<=n; i++)
    {
        c[i].v=ind[i];
        c[i].st=a[i];
    }
    sort(c+1,c+n+1,cmp);
    int br=0;
    for(int i=1; i<=n; i++)
    {
        if(c[i].st>n)
        {
            while(c[i].v!=c[i].st)
            {
                rseq[br]=c[i].v;
                br++;
                c[i].v=next;
                next++;
            }
        }
    }
    return br;
}
long long int fup(long long int base,long long int pow)
{
    long long int otg=1;
    for(int i=0; i<=30; i++)
    {
        if(pow&(1<<i))
        {
            otg*=base;
            otg=otg%maxn;
        }
        base*=base;
        base=base%maxn;
    }
    return otg;
}
bool check()
{
    int br=0;
    for(int i=1; i<=n; i++)
    {
        if(a[i]<=n)
        {
            if(!br)br=a[i];
            else
            {
                if(a[i]!=br)
                {
                    return 0;
                }
            }
        }
        if(used[a[i]])
        {
            return 0;
        }
        used[a[i]]=1;
        if(br)br++;
        if(br>n)br=1;
    }
    return 1;
}
int countReplacement(int n, int seq[])
{
    long long int otg=1,now=n,f=0;
    for(int i=1; i<=n; i++)
    {
        a[i]=seq[i-1];
        if(a[i]<=n)f=1;
    }
    if(!check())return 0;
    sort(a+1,a+n+1);
    for(int i=1; i<=n; i++)
    {
        if(a[i]>now)
        {
            otg=otg*fup(n-i+1,a[i]-now-1);
            otg=otg%maxn;
            now=a[i];
        }
    }
    if(f)return otg;
    else return (otg*n)%maxn;
}
void test()
{
    cin>>n;
    long long int otg=1,now=n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        se[i-1]=a[i];
    }
    if(!check())
    {
        cout<<0<<endl;
        return;
    }
    sort(a+1,a+n+1);
    for(int i=1; i<=n; i++)
    {
        if(a[i]>n)
        {
            otg=otg*fup(n-i+1,a[i]-now-1);
            otg=otg%maxn;
            now=a[i];
        }
    }
    cout<<otg<<endl;
}
/*int main()
{
    speed();
    test();
    return 0;
}
*/

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 122716 KB Output is correct
2 Correct 29 ms 122716 KB Output is correct
3 Correct 29 ms 122532 KB Output is correct
4 Correct 28 ms 122704 KB Output is correct
5 Correct 33 ms 122796 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 122708 KB Output is correct
2 Correct 28 ms 122716 KB Output is correct
3 Correct 27 ms 122588 KB Output is correct
4 Correct 27 ms 122708 KB Output is correct
5 Correct 34 ms 122708 KB Output is correct
6 Correct 32 ms 122940 KB Output is correct
7 Correct 32 ms 123224 KB Output is correct
8 Correct 34 ms 123228 KB Output is correct
9 Correct 29 ms 122716 KB Output is correct
10 Correct 35 ms 123160 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 122708 KB Output is correct
2 Correct 28 ms 122704 KB Output is correct
3 Correct 34 ms 122708 KB Output is correct
4 Correct 30 ms 122712 KB Output is correct
5 Correct 30 ms 122708 KB Output is correct
6 Correct 35 ms 122976 KB Output is correct
7 Correct 36 ms 123400 KB Output is correct
8 Correct 34 ms 123296 KB Output is correct
9 Correct 31 ms 122708 KB Output is correct
10 Correct 34 ms 123216 KB Output is correct
11 Correct 34 ms 122712 KB Output is correct
12 Correct 29 ms 122708 KB Output is correct
13 Correct 33 ms 122968 KB Output is correct
14 Correct 30 ms 122716 KB Output is correct
15 Correct 36 ms 123416 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 122716 KB Output is correct
2 Correct 29 ms 122704 KB Output is correct
3 Correct 29 ms 122708 KB Output is correct
4 Correct 29 ms 122708 KB Output is correct
5 Correct 34 ms 122704 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 122716 KB Output is correct
2 Correct 33 ms 122640 KB Output is correct
3 Correct 30 ms 122708 KB Output is correct
4 Correct 31 ms 122712 KB Output is correct
5 Correct 29 ms 122712 KB Output is correct
6 Correct 35 ms 122704 KB Output is correct
7 Correct 30 ms 122716 KB Output is correct
8 Correct 29 ms 122752 KB Output is correct
9 Correct 31 ms 122716 KB Output is correct
10 Correct 29 ms 122712 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 122656 KB Output is correct
2 Correct 30 ms 122716 KB Output is correct
3 Correct 29 ms 122740 KB Output is correct
4 Correct 29 ms 122688 KB Output is correct
5 Correct 30 ms 122716 KB Output is correct
6 Correct 35 ms 122700 KB Output is correct
7 Correct 31 ms 122712 KB Output is correct
8 Correct 30 ms 122708 KB Output is correct
9 Correct 29 ms 122708 KB Output is correct
10 Correct 29 ms 122704 KB Output is correct
11 Correct 40 ms 124240 KB Output is correct
12 Correct 40 ms 124500 KB Output is correct
13 Correct 37 ms 123988 KB Output is correct
14 Correct 37 ms 124276 KB Output is correct
15 Correct 41 ms 124776 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 122708 KB Output is correct
2 Correct 29 ms 122732 KB Output is correct
3 Correct 28 ms 122716 KB Output is correct

Subtask #8
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 122604 KB Output is correct
2 Correct 34 ms 122600 KB Output is correct
3 Correct 27 ms 122716 KB Output is correct
4 Correct 28 ms 122724 KB Output is correct
5 Correct 28 ms 122616 KB Output is correct
6 Correct 28 ms 122708 KB Output is correct
7 Correct 26 ms 122704 KB Output is correct
8 Correct 27 ms 122716 KB Output is correct

Subtask #9
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 122708 KB Output is correct
2 Correct 33 ms 122708 KB Output is correct
3 Correct 28 ms 122708 KB Output is correct
4 Correct 29 ms 122704 KB Output is correct
5 Correct 32 ms 122516 KB Output is correct
6 Correct 28 ms 122716 KB Output is correct
7 Correct 28 ms 122564 KB Output is correct
8 Correct 28 ms 122704 KB Output is correct
9 Correct 42 ms 123204 KB Output is correct
10 Correct 40 ms 123220 KB Output is correct
11 Correct 34 ms 122844 KB Output is correct
12 Correct 34 ms 122960 KB Output is correct
13 Correct 29 ms 122744 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 122716 KB Output is correct
2 Correct 29 ms 122708 KB Output is correct
3 Correct 34 ms 122712 KB Output is correct
4 Correct 33 ms 122752 KB Output is correct
5 Correct 31 ms 122704 KB Output is correct
6 Correct 28 ms 122712 KB Output is correct
7 Correct 27 ms 122716 KB Output is correct
8 Correct 33 ms 122660 KB Output is correct
9 Correct 44 ms 123316 KB Output is correct
10 Correct 41 ms 123224 KB Output is correct
11 Correct 35 ms 122716 KB Output is correct
12 Correct 36 ms 122964 KB Output is correct
13 Correct 32 ms 122712 KB Output is correct
14 Correct 54 ms 123988 KB Output is correct
15 Correct 52 ms 124244 KB Output is correct
16 Correct 32 ms 122964 KB Output is correct
17 Correct 43 ms 123680 KB Output is correct
18 Correct 39 ms 123184 KB Output is correct