Submission #320051

#	Time	Username	Problem	Language	Result	Execution time	Memory
320051		keta_tsimakuridze	Gondola (IOI14_gondola)	C++14	100 / 100	82 ms	12772 KiB

gondola

#include<bits/stdc++.h>
#include "gondola.h"
#define f first
#define s second
#define mp make_pair
#include <stdio.h>
#include <assert.h>
using namespace std;
const int mod=1e9+9;
const int N=2e5+5;
int c[N];
map<long long,int> fix;
int valid(int n, int a[])
{

	vector<pair<int,int> > V;
  for(int i=0;i<n;i++){
  	if(fix[a[i]]) return 0;
  	if(a[i]<=n) {
  		V.push_back(mp(a[i],i));
	  }
	fix[a[i]]=1;
  }	
  for(int i=1;i<V.size();i++){
  	if(V[i].f>V[i-1].f){
	  if(V[i].f-V[i-1].f!=V[i].s-V[i-1].s)	return 0;}
	  else {
	  	if(V[i].s-V[i-1].s!=n-V[i-1].f+V[i].f) return 0;
	  }
  }
  return 1;
}
//--------------------
int replacement(int n, int a[], int b[])
{ 
	int mx=0;
	int ind=-1;
	for(int i=0;i<n;i++){
		mx=max(mx,a[i]);
		if(a[i]<=n) ind=i;
		fix[a[i]]=i+1; }
	if(ind==-1){
	
	for(int i=0;i<n;i++)
	c[i]=i+1;}
	else {
		for(int i=ind;i<n;i++){
			c[i]=(a[ind]-1+i-ind)%n;
			c[i]++;
		}
		for(int i=ind-1;i>=0;i--){
			c[i]=(a[ind]-1-(ind-i)+n)%n;
			c[i]++;
		}
	}
	for(int i=n+1;i<=mx;i++){
		if(fix[i]) {
			b[i-n-1]=c[fix[i]-1];
			c[fix[i]-1]=i;
		}
		else {
			b[i-n-1]=c[fix[mx]-1];
			c[fix[mx]-1]=i;
		}
	}
  return mx-n;
}

//----------------------
long long pwr(int u,int v){
	if(v==1) return u;
	if(v%2) return pwr(u,v-1)*u%mod;
	long long p=pwr(u,v/2);
	return p*p%mod;
}
int countReplacement(int n, int a[])
{
	vector<int>V;
	long long ans=1;
	for(int i=0;i<n;i++){
	if(fix[a[i]]) return 0;
	if(a[i]>n) V.push_back(a[i]); fix[a[i]]=1;}
	
	if(!V.size())return 1;
	V.push_back(n);
	sort(V.begin(),V.end());
	for(int i=1;i<V.size();i++){
		if(V[i]==V[i-1]+1) continue;
		ans*=pwr(V.size()-i,V[i]-V[i-1]-1);
		ans%=mod;
	}
	if(V.size()==n+1)ans*=n,ans%=mod;
	
	
  return ans;
}

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:24:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for(int i=1;i<V.size();i++){
      |               ~^~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:82:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   82 |  if(a[i]>n) V.push_back(a[i]); fix[a[i]]=1;}
      |  ^~
gondola.cpp:82:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   82 |  if(a[i]>n) V.push_back(a[i]); fix[a[i]]=1;}
      |                                ^~~
gondola.cpp:87:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for(int i=1;i<V.size();i++){
      |              ~^~~~~~~~~
gondola.cpp:92:13: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   92 |  if(V.size()==n+1)ans*=n,ans%=mod;
      |     ~~~~~~~~^~~~~

• 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