oj.uz

Submission #1017717

# Submission time Handle Problem Language Result Execution time Memory
1017717 2024-07-09T09:38:04 Z vivkostov Gondola (IOI14_gondola) C++14
60 / 100
 15 ms 7772 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],used[1000005],ind[200005];
cell c[200005];
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;
}
int countReplacement(int n, int seq[])
{
    long long int otg=1,now=n;
    for(int i=1;i<=n;i++)
    {
        a[i]=seq[i-1];
    }
    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];
        }
    }
    if(!valid(n,seq))return 0;
    return otg;
}
/*int main()
{
    speed();
    read();
    return 0;
}
*/

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 6 ms 4700 KB Output is correct
7 Correct 8 ms 4444 KB Output is correct
8 Correct 8 ms 4700 KB Output is correct
9 Correct 3 ms 4444 KB Output is correct
10 Correct 6 ms 4700 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 5 ms 4700 KB Output is correct
7 Correct 9 ms 4444 KB Output is correct
8 Correct 8 ms 4696 KB Output is correct
9 Correct 2 ms 4440 KB Output is correct
10 Correct 11 ms 4700 KB Output is correct
11 Correct 1 ms 4448 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 5 ms 4804 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 7 ms 4544 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6496 KB Output is correct
2 Correct 1 ms 6496 KB Output is correct
3 Correct 1 ms 6500 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6500 KB Output is correct
6 Correct 1 ms 6500 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6604 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 10 ms 7004 KB Output is correct
12 Correct 15 ms 7260 KB Output is correct
13 Correct 10 ms 7256 KB Output is correct
14 Correct 13 ms 7220 KB Output is correct
15 Correct 13 ms 7772 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4440 KB Output is correct

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4548 KB Output is correct
4 Correct 2 ms 4440 KB Output is correct
5 Incorrect 1 ms 4444 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Incorrect 1 ms 4536 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 1 ms 4536 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Incorrect 1 ms 4444 KB Output isn't correct
6 Halted 0 ms 0 KB -