Submission #87990

#	Time	Username	Problem	Language	Result	Execution time	Memory
87990		Pajaraja	Gondola (IOI14_gondola)	C++17	100 / 100	88 ms	18348 KiB

gondola

#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 (stderr)

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 5 / 5
• Subtask 8: 15 / 15
• Subtask 9: 15 / 15
• Subtask 10: 10 / 10