oj.uz

Submission #345694

# Submission time Handle Problem Language Result Execution time Memory
345694 2021-01-07T21:55:54 Z ogibogi2004 Gondola (IOI14_gondola) C++14
100 / 100
 69 ms 6380 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+9;
ll fastpow(ll x,ll p)
{
	if(p==0)return 1;
	ll t=fastpow(x,p/2);
	t*=t;t%=mod;
	if(p%2==1)t*=x;
	t%=mod;
	return t;
}
int valid(int n, int inputSeq[])
{
	vector<int>v;
	set<int>s;
	set<int>s2;
	for(int i=0;i<n;i++)
	{
		s.insert(inputSeq[i]);
		if(inputSeq[i]<=n)
		{
			int t=inputSeq[i]-i;
			if(t<0)t+=n;
			s2.insert(t);
		}
	}
	if(s.size()!=n)return 0;
	if(s2.size()>1)return 0;
	return 1;
	int t=v.size();
	for(int i=0;i<t;i++)v.push_back(v[i]);
	int cnt=0;
	bool ok=0;
	for(int i=1;i<v.size();i++)
	{
		if(v[i]>v[i-1])cnt++;
		else cnt=0;
		if(cnt==t-1)
		{
			ok=1;
		}
	}
	return ok;
	return -1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	if(!valid(n,gondolaSeq))return 0;
	int s=0,j=-1;
	int real[n];
	for(int i=0;i<n;i++)
	{
		if(gondolaSeq[i]<=n)
		{
			j=i;
		}
	}
	if(j==-1)
	{
		for(int i=0;i<n;i++)real[i]=i+1;
	}
	else
	{
		for(int i=0;i<n;i++)
		{
			real[(j+i)%n]=(gondolaSeq[j]+i-1)%n+1;
		}
	}
	vector<pair<int,int> >v;
	for(int i=0;i<n;i++)
	{
		if(gondolaSeq[i]!=real[i])
		{
			v.push_back({gondolaSeq[i],real[i]});
		}
	}
	sort(v.begin(),v.end());
	vector<int>reps;
	int nxt=n+1;
	for(int i=0;i<v.size();i++)
	{
		reps.push_back(v[i].second);
		while(nxt!=v[i].first)
		{
			reps.push_back(nxt);
			nxt++;
		}
		nxt++;
	}
	for(int i=0;i<reps.size();i++)
	{
		replacementSeq[i]=reps[i];
	}
	return reps.size();
}

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

int countReplacement(int n, int inputSeq[])
{
	if(!valid(n,inputSeq))return 0;
	int s=0,j=-1;
	int real[n];
	for(int i=0;i<n;i++)
	{
		if(inputSeq[i]<=n)
		{
			j=i;
		}
	}
	if(j==-1)
	{
		for(int i=0;i<n;i++)real[i]=i+1;
	}
	else
	{
		for(int i=0;i<n;i++)
		{
			real[(j+i)%n]=(inputSeq[j]+i-1)%n+1;
		}
	}
	vector<pair<int,int> >v;
	for(int i=0;i<n;i++)
	{
		if(inputSeq[i]!=real[i])
		{
			v.push_back({inputSeq[i],real[i]});
		}
	}
	sort(v.begin(),v.end());
	int nxt=n+1;
	ll ret=1;
	for(int i=0;i<v.size();i++)
	{
		ret*=fastpow(v.size()-i,v[i].first-nxt);
		ret%=mod;
		nxt=v[i].first+1;
	}
	if(j==-1)
	{
		ret*=n;
		ret%=mod;
	}
	return ret;
	return -3;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:30:13: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |  if(s.size()!=n)return 0;
      |     ~~~~~~~~^~~
gondola.cpp:37:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(int i=1;i<v.size();i++)
      |              ~^~~~~~~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:86:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  for(int i=0;i<v.size();i++)
      |              ~^~~~~~~~~
gondola.cpp:96:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  for(int i=0;i<reps.size();i++)
      |              ~^~~~~~~~~~~~
gondola.cpp:55:6: warning: unused variable 's' [-Wunused-variable]
   55 |  int s=0,j=-1;
      |      ^
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:139:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |  for(int i=0;i<v.size();i++)
      |              ~^~~~~~~~~
gondola.cpp:108:6: warning: unused variable 's' [-Wunused-variable]
  108 |  int s=0,j=-1;
      |      ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 ms 364 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 ms 396 KB Output is correct
6 Correct 12 ms 2284 KB Output is correct
7 Correct 51 ms 4972 KB Output is correct
8 Correct 29 ms 3948 KB Output is correct
9 Correct 9 ms 1516 KB Output is correct
10 Correct 29 ms 4612 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 1 ms 380 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 12 ms 2284 KB Output is correct
7 Correct 47 ms 4972 KB Output is correct
8 Correct 25 ms 3948 KB Output is correct
9 Correct 7 ms 1516 KB Output is correct
10 Correct 28 ms 4612 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 17 ms 2156 KB Output is correct
14 Correct 0 ms 364 KB Output is correct
15 Correct 65 ms 6124 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 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 1 ms 364 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 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 1 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 384 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 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 1 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
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 30 ms 4588 KB Output is correct
12 Correct 33 ms 5228 KB Output is correct
13 Correct 27 ms 2924 KB Output is correct
14 Correct 29 ms 4612 KB Output is correct
15 Correct 39 ms 3012 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 0 ms 364 KB Output is correct
3 Correct 1 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 1 ms 320 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 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 1 ms 388 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 50 ms 4852 KB Output is correct
10 Correct 36 ms 4016 KB Output is correct
11 Correct 13 ms 1924 KB Output is correct
12 Correct 16 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 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 388 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 44 ms 4844 KB Output is correct
10 Correct 35 ms 4076 KB Output is correct
11 Correct 12 ms 1924 KB Output is correct
12 Correct 15 ms 2048 KB Output is correct
13 Correct 4 ms 748 KB Output is correct
14 Correct 53 ms 5740 KB Output is correct
15 Correct 69 ms 6380 KB Output is correct
16 Correct 10 ms 1388 KB Output is correct
17 Correct 39 ms 4460 KB Output is correct
18 Correct 23 ms 2924 KB Output is correct