oj.uz

Submission #320859

# Submission time Handle Problem Language Result Execution time Memory
320859 2020-11-10T06:08:14 Z daniel920712 Gondola (IOI14_gondola) C++14
100 / 100
 70 ms 6372 KB 
#include "gondola.h"
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
using namespace std;
map < int , int > con;
int all[100005];
set < int > have;
priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > how ;
int valid(int n, int inputSeq[])
{
    int what,ok=1,i;
    for(i=1;i<=n;i++) all[i]=1e9;
    for(i=0;i<n;i++)
    {
        con[inputSeq[i]]++;
        if(con[inputSeq[i]]>=2) ok=0;
        if(inputSeq[i]>n) continue;
        all[inputSeq[i]]=(inputSeq[i]-i+n)%n;
        what=(inputSeq[i]-i+n)%n;
    }
    for(i=1;i<=n;i++) if(all[i]!=1000000000&&all[i]!=what) ok=0;
    return ok;
}

//----------------------
bool F(pair < int , int > a,pair < int , int > b)
{
    return a.second<b.second;
}
pair < int , int > All[100005];
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    int now=0,con=0,where=0,big=0,t,i,x,y,nxt;
    for(i=0;i<n;i++)
    {
        if(gondolaSeq[i]>n) con++;
        else where=i;
    }
    if(con==n) for(i=0;i<n;i++) All[i]=make_pair(i+1,gondolaSeq[i]);
    else
    {
        x=0;
        y=gondolaSeq[where];
        for(i=where;x<n;i++,i%=n,x++)
        {
            All[i]=make_pair(y,gondolaSeq[i]);
            y++;
            if(y>n) y%=n;
        }

    }
    nxt=n+1;
    sort(All,All+n,F);
    for(i=0;i<n;i++)
    {
        while(All[i].first!=All[i].second)
        {
            replacementSeq[now++]=All[i].first;
            All[i].first=nxt;
            nxt++;
        }
    }

    return now;


}

//----------------------
long long MOD=1e9+9;
long long Pow(int a,int b)
{
    if(b==0) return 1;
    long long t=Pow(a,b/2);
    t=t*t%MOD;
    if(b%2) t=t*a%MOD;
    return t;
}
int countReplacement(int n, int inputSeq[])
{
    int what,ok=1,i,x=0,now=n,tt=n;
    long long ans=1;
    for(i=1;i<=n;i++) all[i]=2e9;
    for(i=0;i<n;i++)
    {
        con[inputSeq[i]]++;
        if(con[inputSeq[i]]>=2) ok=0;
        if(inputSeq[i]>n)
        {
            x++;
            continue;
        }
        all[inputSeq[i]]=(inputSeq[i]-i+n)%n;
        what=(inputSeq[i]-i+n)%n;
    }

    for(i=1;i<=n;i++) if(all[i]!=2000000000&&all[i]!=what) ok=0;
    if(ok==0) return 0;
    if(x==0) return 1;
    if(x==n) ans=n;
    sort(inputSeq,inputSeq+n);
    for(i=0;i<n;i++)
    {
        if(inputSeq[i]<=n) now--;
        else
        {
            ans*=Pow(now,inputSeq[i]-tt-1);
            ans%=MOD;
            now--;
            tt=inputSeq[i];
        }
    }
    return (int) ans%MOD;

}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:36:29: warning: unused variable 'big' [-Wunused-variable]
   36 |     int now=0,con=0,where=0,big=0,t,i,x,y,nxt;
      |                             ^~~
gondola.cpp:36:35: warning: unused variable 't' [-Wunused-variable]
   36 |     int now=0,con=0,where=0,big=0,t,i,x,y,nxt;
      |                                   ^
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:24:44: warning: 'what' may be used uninitialized in this function [-Wmaybe-uninitialized]
   24 |     for(i=1;i<=n;i++) if(all[i]!=1000000000&&all[i]!=what) ok=0;
      |                          ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:100:44: warning: 'what' may be used uninitialized in this function [-Wmaybe-uninitialized]
  100 |     for(i=1;i<=n;i++) if(all[i]!=2000000000&&all[i]!=what) ok=0;
      |                          ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 15 ms 2540 KB Output is correct
7 Correct 38 ms 4196 KB Output is correct
8 Correct 31 ms 4332 KB Output is correct
9 Correct 9 ms 1644 KB Output is correct
10 Correct 35 ms 4964 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 15 ms 2540 KB Output is correct
7 Correct 39 ms 4196 KB Output is correct
8 Correct 30 ms 4452 KB Output is correct
9 Correct 9 ms 1644 KB Output is correct
10 Correct 36 ms 5088 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 0 ms 364 KB Output is correct
13 Correct 19 ms 2404 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 63 ms 5240 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 396 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 1 ms 360 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 16 ms 1516 KB Output is correct
12 Correct 23 ms 1664 KB Output is correct
13 Correct 17 ms 1516 KB Output is correct
14 Correct 15 ms 1516 KB Output is correct
15 Correct 23 ms 2528 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 51 ms 4708 KB Output is correct
10 Correct 40 ms 3812 KB Output is correct
11 Correct 18 ms 1644 KB Output is correct
12 Correct 21 ms 2028 KB Output is correct
13 Correct 4 ms 748 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 48 ms 4452 KB Output is correct
10 Correct 38 ms 3812 KB Output is correct
11 Correct 14 ms 1644 KB Output is correct
12 Correct 18 ms 1900 KB Output is correct
13 Correct 4 ms 748 KB Output is correct
14 Correct 68 ms 5860 KB Output is correct
15 Correct 70 ms 6372 KB Output is correct
16 Correct 13 ms 1388 KB Output is correct
17 Correct 46 ms 4456 KB Output is correct
18 Correct 26 ms 2664 KB Output is correct