Submission #59261

#	Time	Username	Problem	Language	Result	Execution time	Memory
59261		TadijaSebez	Gondola (IOI14_gondola)	C++11	100 / 100	56 ms	13196 KiB

gondola

#include "gondola.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
bool Check(vector<int> a)
{
	int n=a.size(),i,j,k;
	for(i=0;i<n;i++) if(a[i]<=n) break;
	if(i==n)
	{
		sort(a.begin(),a.end());
		for(i=1;i<n;i++) if(a[i]==a[i-1]) return 0;
		return 1;
	}
	vector<int> b;
	j=i-a[i]+1;
	if(j<0)
	{
		for(k=j+n;k<n;k++) b.pb(a[k]);
		for(k=0;k<j+n;k++) b.pb(a[k]);
	}
	else
	{
		for(k=j;k<n;k++) b.pb(a[k]);
		for(k=0;k<j;k++) b.pb(a[k]);
	}
	//for(i=0;i<n;i++) printf("%i ",b[i]);printf("\n");
	for(i=0;i<n;i++) if(b[i]<=n && b[i]!=i+1) return 0;
	for(i=0;i<n;i++) if(b[i]==0) return 0;
	sort(b.begin(),b.end());
	for(i=1;i<n;i++) if(b[i]==b[i-1]) return 0;
	return 1;
}
vector<int> Replace(vector<int> a)
{
	int n=a.size(),i,j,k;vector<int> sol;
	for(i=0;i<n;i++) if(a[i]<=n) break;
	if(i==n)
	{
		vector<pair<int,int> > tmp;
		for(i=0;i<n;i++) tmp.pb(mp(a[i],i+1));
		sort(tmp.begin(),tmp.end());
		int m=n;
		for(i=0;i<tmp.size();i++)
		{
			sol.pb(tmp[i].second);m++;
			while(m<tmp[i].first)
			{
				sol.pb(m);m++;
			}
		}
		return sol;
	}
	vector<int> b;
	j=i-a[i]+1;
	if(j<0)
	{
		for(k=j+n;k<n;k++) b.pb(a[k]);
		for(k=0;k<j+n;k++) b.pb(a[k]);
	}
	else
	{
		for(k=j;k<n;k++) b.pb(a[k]);
		for(k=0;k<j;k++) b.pb(a[k]);
	}
	vector<pair<int,int> > tmp;
	int m=n;
	for(i=0;i<n;i++) if(b[i]>n) tmp.pb(mp(b[i],i+1));
	sort(tmp.begin(),tmp.end());
	for(i=0;i<tmp.size();i++)
	{
		sol.pb(tmp[i].second);m++;
		while(m<tmp[i].first)
		{
			sol.pb(m);m++;
		}
	}
	return sol;
}
const int mod=1e9+9;
int pow(int x, int k)
{
	int ret=1;
	for(;k;k>>=1,x=(ll)x*x%mod) if(k&1) ret=(ll)ret*x%mod;
	return ret;
}
int Count(vector<int> a)
{
	vector<int> tmp;
	int i,j,k,n=a.size();
	for(i=0;i<n;i++) if(a[i]>n) tmp.pb(a[i]);
	sort(tmp.begin(),tmp.end());
	int last=n,sol=1,sz=tmp.size();
	for(i=0;i<sz;i++)
	{
		int dist=tmp[i]-last-1;
		sol=(ll)sol*pow(sz-i,dist)%mod;
		last=tmp[i];
	}
	if(sz==n) sol=(ll)sol*n%mod;
	return sol;
}
int valid(int n, int a[])
{
	int i;
	vector<int> b;
	for(i=0;i<n;i++) b.pb(a[i]);
	return (int)Check(b);
}
int replacement(int n, int a[], int sol[])
{
	int i;
	vector<int> b;
	for(i=0;i<n;i++) b.pb(a[i]);
	vector<int> ans=Replace(b);
	for(i=0;i<ans.size();i++) sol[i]=ans[i];
	return ans.size();
}
int countReplacement(int n, int a[])
{
	int i;
	vector<int> b;
	for(i=0;i<n;i++) b.pb(a[i]);
	if(Check(b)) return Count(b);
	else return 0;
}

Compilation message (stderr)

gondola.cpp: In function 'std::vector<int> Replace(std::vector<int>)':
gondola.cpp:48:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0;i<tmp.size();i++)
           ~^~~~~~~~~~~
gondola.cpp:74:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<tmp.size();i++)
          ~^~~~~~~~~~~
gondola.cpp: In function 'int Count(std::vector<int>)':
gondola.cpp:94:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j,k,n=a.size();
        ^
gondola.cpp:94:10: warning: unused variable 'k' [-Wunused-variable]
  int i,j,k,n=a.size();
          ^
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:120:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<ans.size();i++) sol[i]=ans[i];
          ~^~~~~~~~~~~

• 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