oj.uz

Submission #247637

# Submission time Handle Problem Language Result Execution time Memory
247637 2020-07-11T18:44:41 Z Evirir Gondola (IOI14_gondola) C++17
100 / 100
 93 ms 6384 KB 
#include "gondola.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
void amin(ll &a, ll b){ a=min(a,b); }
void amax(ll &a, ll b){ a=max(a,b); }
void YES(){cout<<"YES\n";} void NO(){cout<<"NO\n";}
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
const ll INF = ll(1e18);
const int MOD = 1e9+9;

bool DEBUG = 0;
const int MAXN = 100005;
const int MAXA = 250005;

ll add(ll a,ll b)
{
	a+=b; a%=MOD;
	if(a<0) a+=MOD;
	return a;
}
ll mult(ll a, ll b)
{
	if(a>MOD) a%=MOD;
	if(b>MOD) b%=MOD;
	ll ans=(a*b)%MOD;
	if(ans<0) ans+=MOD;
	return ans;
}
ll pw(ll a, ll b)
{
	ll r=1;
	while(b){
		if(b&1) r=mult(r,a);
		a=mult(a,a);
		b>>=1;
	}
	return r;
}
ll inverse(ll a)
{
	return pw(a,MOD-2);
}

int valid(int n, int inputSeq[])
{
	int minid=0;
	forn(i,0,n){
		if(inputSeq[minid]>inputSeq[i]){
			minid=i;
		}
	}
	
	int tmp[n];
	forn(i,0,n){
		tmp[i]=inputSeq[(minid+i)%n];
	}
	forn(i,0,n) inputSeq[i]=tmp[i];
	
	set<ll> used;
	int last=-1;
	for(int i=0;i<n;i++){
		if(used.find(inputSeq[i])!=used.end()) return 0;
		used.insert(inputSeq[i]);
		
		if(inputSeq[i]<=n){
			if(last!=-1 && inputSeq[i]-inputSeq[last]!=i-last) return 0;
			last=i;
		}
	}
	
	return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	assert(valid(n, gondolaSeq));
	
	int loc[MAXA];
	mset(loc,-1);
	
	int large=0;
	for(int i=0;i<n;i++){
		loc[gondolaSeq[i]]=i;
		if(gondolaSeq[i]>gondolaSeq[large]){
			large=i;
		}
	}
	
	int a[n];
	int start=0,val=1;
	for(int i=0;i<n;i++){
		if(gondolaSeq[i]<=n){
			start=i;
			val=gondolaSeq[i];
			break;
		}
	}
	for(int i=start;;){
		a[i]=val++;
		if(val==n+1) val=1;
		
		i=(i+1)%n;
		if(i==start) break;
	}
	
	int ptr=0;
	for(int i=n+1;i<=gondolaSeq[large];i++){
		if(loc[i] == -1){
			//cout<<"Not found\n";
			replacementSeq[ptr++]=a[large];
			a[large]=i;
		}
		else{
			//cout<<"Found\n";
			replacementSeq[ptr++] = a[loc[i]];
			a[loc[i]]=i;
		}
	}
	
	return ptr;
}

int countReplacement(int n, int inputSeq[])
{
	if(!valid(n, inputSeq)) return 0;
	
	vi v;
	for(int i=0;i<n;i++){
		v.pb(inputSeq[i]);
	}
	sort(v.begin(), v.end(), greater<ll>());
	
	ll ans=1;
	if(v.back()>n) ans=n;
	
	ll cur=0;
	while(v.size() && v.back()<=n) v.pop_back();
	cur=v.size();
	v.pb(n);
	reverse(v.begin(), v.end());
	
	for(int i=1;i<v.size();i++){
		ans=mult(ans, pw(cur, v[i]-v[i-1]-1));
		cur--;
	}
	
	return ans;
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:163:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<v.size();i++){
              ~^~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 20 ms 2432 KB Output is correct
7 Correct 18 ms 1024 KB Output is correct
8 Correct 35 ms 4216 KB Output is correct
9 Correct 13 ms 1536 KB Output is correct
10 Correct 42 ms 4856 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 24 ms 2424 KB Output is correct
7 Correct 18 ms 1024 KB Output is correct
8 Correct 35 ms 4088 KB Output is correct
9 Correct 13 ms 1536 KB Output is correct
10 Correct 51 ms 4856 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 11 ms 640 KB Output is correct
14 Correct 5 ms 256 KB Output is correct
15 Correct 19 ms 1024 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1280 KB Output is correct
2 Correct 5 ms 1280 KB Output is correct
3 Correct 5 ms 1280 KB Output is correct
4 Correct 5 ms 1280 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Correct 5 ms 1280 KB Output is correct
7 Correct 5 ms 1280 KB Output is correct
8 Correct 5 ms 1280 KB Output is correct
9 Correct 5 ms 1280 KB Output is correct
10 Correct 5 ms 1280 KB Output is correct
11 Correct 40 ms 5624 KB Output is correct
12 Correct 46 ms 6264 KB Output is correct
13 Correct 32 ms 3840 KB Output is correct
14 Correct 39 ms 5624 KB Output is correct
15 Correct 29 ms 3968 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 4 ms 256 KB Output is correct
9 Correct 53 ms 4344 KB Output is correct
10 Correct 43 ms 3704 KB Output is correct
11 Correct 18 ms 1536 KB Output is correct
12 Correct 22 ms 1792 KB Output is correct
13 Correct 8 ms 640 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 4 ms 256 KB Output is correct
9 Correct 56 ms 4344 KB Output is correct
10 Correct 44 ms 3704 KB Output is correct
11 Correct 18 ms 1536 KB Output is correct
12 Correct 21 ms 1792 KB Output is correct
13 Correct 8 ms 640 KB Output is correct
14 Correct 74 ms 5752 KB Output is correct
15 Correct 93 ms 6384 KB Output is correct
16 Correct 16 ms 1408 KB Output is correct
17 Correct 53 ms 4472 KB Output is correct
18 Correct 28 ms 2560 KB Output is correct