oj.uz

Submission #87990

# Submission time Handle Problem Language Result Execution time Memory
87990 2018-12-03T10:59:18 Z Pajaraja Gondola (IOI14_gondola) C++17
100 / 100
 88 ms 18348 KB 
#include "gondola.h"
#include <bits/stdc++.h>
#define MOD 1000000009
using namespace std;
map<int,bool> vi;
int a[100000],b[100000];
pair<int,int> c[100000];
long long fastpow(long long x,int exp)
{
	if(exp==0) return 1;
	if(exp%2==0) 
	{
	    long long y=fastpow(x,exp/2);
	    return (y*y)%MOD;
	}
	long long y=fastpow(x,exp-1);
	return (x*y)%MOD;
}
int valid(int n, int inputSeq[])
{
	int poz=0;
	for(int i=0;i<n;i++) a[i]=inputSeq[i];
	for(int i=0;i<n;i++)
	{
		if(vi[a[i]]==true) return 0;
		vi[a[i]]=true;
	}
	for(int i=0;i<n;i++) if(a[i]<=n) poz=(i+n+1-a[i])%n;
	if(poz==-1) return 1;
	for(int i=poz;i<n;i++) b[i-poz]=a[i];
	for(int i=0;i<poz;i++) b[i+n-poz]=a[i];
	for(int i=0;i<n;i++) if(b[i]!=i+1&&b[i]<=n) return 0;
	return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	int poz=0,max=0,st=n+1,cnt=0;;
	for(int i=0;i<n;i++) a[i]=gondolaSeq[i];
	for(int i=0;i<n;i++) if(a[i]<=n) poz=(i+n+1-a[i])%n;
	if(poz==-1) return 1;
	for(int i=poz;i<n;i++) c[i-poz].first=a[i];
	for(int i=0;i<poz;i++) c[i+n-poz].first=a[i];
	for(int i=0;i<n;i++) c[i].second=i+1;
	sort(c,c+n);
	for(int i=0;i<n;i++)
	{
		if(c[i].first==c[i].second) continue;
		 replacementSeq[cnt]=c[i].second;
		 cnt++;
		 while(st<c[i].first)
		 {
		 	replacementSeq[cnt]=st;
		 	cnt++;
		 	st++;;
		 }
		 st++;
	}
	return cnt;
}

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

int countReplacement(int n, int inputSeq[])
{
	int poz=0,max=0,st=n+1,cnt=0;
	long long sol=1;
	for(int i=0;i<n;i++) a[i]=inputSeq[i];
	for(int i=0;i<n;i++) if(a[i]<=n) poz=(i+n+1-a[i])%n;
	for(int i=poz;i<n;i++) c[i-poz].first=a[i];
	for(int i=0;i<poz;i++) c[i+n-poz].first=a[i];
	for(int i=0;i<n;i++) c[i].second=i+1;
	sort(c,c+n);
	if(!valid(n,inputSeq)) return 0;
	for(int i=0;i<n;i++)
	{
		 if(c[i].first==c[i].second) continue;
		 long long r=fastpow(n-i,c[i].first-st);
		 sol=(sol*r)%MOD;
		 st=c[i].first+1;
	}
	if(c[0].first>n) 
	{
		sol*=n;
		sol%=MOD;
	}
	return sol;
}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:40:12: warning: unused variable 'max' [-Wunused-variable]
  int poz=0,max=0,st=n+1,cnt=0;;
            ^~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:68:12: warning: unused variable 'max' [-Wunused-variable]
  int poz=0,max=0,st=n+1,cnt=0;
            ^~~
gondola.cpp:68:25: warning: unused variable 'cnt' [-Wunused-variable]
  int poz=0,max=0,st=n+1,cnt=0;
                         ^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 852 KB Output is correct
2 Correct 2 ms 856 KB Output is correct
3 Correct 2 ms 876 KB Output is correct
4 Correct 3 ms 1008 KB Output is correct
5 Correct 3 ms 1072 KB Output is correct
6 Correct 20 ms 3532 KB Output is correct
7 Correct 15 ms 3532 KB Output is correct
8 Correct 37 ms 6336 KB Output is correct
9 Correct 13 ms 6336 KB Output is correct
10 Correct 48 ms 7668 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7668 KB Output is correct
2 Correct 2 ms 7668 KB Output is correct
3 Correct 2 ms 7668 KB Output is correct
4 Correct 2 ms 7668 KB Output is correct
5 Correct 2 ms 7668 KB Output is correct
6 Correct 21 ms 7668 KB Output is correct
7 Correct 15 ms 7668 KB Output is correct
8 Correct 35 ms 8248 KB Output is correct
9 Correct 12 ms 8248 KB Output is correct
10 Correct 46 ms 9548 KB Output is correct
11 Correct 2 ms 9548 KB Output is correct
12 Correct 2 ms 9548 KB Output is correct
13 Correct 26 ms 9548 KB Output is correct
14 Correct 2 ms 9548 KB Output is correct
15 Correct 67 ms 10428 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10428 KB Output is correct
2 Correct 2 ms 10428 KB Output is correct
3 Correct 2 ms 10428 KB Output is correct
4 Correct 2 ms 10428 KB Output is correct
5 Correct 2 ms 10428 KB Output is correct
6 Correct 3 ms 10428 KB Output is correct
7 Correct 3 ms 10428 KB Output is correct
8 Correct 3 ms 10428 KB Output is correct
9 Correct 3 ms 10428 KB Output is correct
10 Correct 3 ms 10428 KB Output is correct
11 Correct 15 ms 10428 KB Output is correct
12 Correct 17 ms 10428 KB Output is correct
13 Correct 18 ms 10428 KB Output is correct
14 Correct 15 ms 10428 KB Output is correct
15 Correct 24 ms 10428 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10428 KB Output is correct
2 Correct 3 ms 10428 KB Output is correct
3 Correct 2 ms 10428 KB Output is correct
4 Correct 2 ms 10428 KB Output is correct
5 Correct 3 ms 10428 KB Output is correct
6 Correct 2 ms 10428 KB Output is correct
7 Correct 2 ms 10428 KB Output is correct
8 Correct 2 ms 10428 KB Output is correct
9 Correct 60 ms 13020 KB Output is correct
10 Correct 48 ms 13020 KB Output is correct
11 Correct 18 ms 13020 KB Output is correct
12 Correct 22 ms 13020 KB Output is correct
13 Correct 7 ms 13020 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13020 KB Output is correct
2 Correct 3 ms 13020 KB Output is correct
3 Correct 2 ms 13020 KB Output is correct
4 Correct 2 ms 13020 KB Output is correct
5 Correct 3 ms 13020 KB Output is correct
6 Correct 2 ms 13020 KB Output is correct
7 Correct 3 ms 13020 KB Output is correct
8 Correct 2 ms 13020 KB Output is correct
9 Correct 58 ms 14460 KB Output is correct
10 Correct 46 ms 14460 KB Output is correct
11 Correct 17 ms 14460 KB Output is correct
12 Correct 21 ms 14460 KB Output is correct
13 Correct 6 ms 14460 KB Output is correct
14 Correct 78 ms 16760 KB Output is correct
15 Correct 88 ms 18348 KB Output is correct
16 Correct 15 ms 18348 KB Output is correct
17 Correct 58 ms 18348 KB Output is correct
18 Correct 29 ms 18348 KB Output is correct