Submission #865827

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
865827	2023-10-24T19:23:22 Z	Huseyn123	Gondola (IOI14_gondola)	C++17	100 / 100	43 ms	6156 KB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
#define MAX 200001
#define INF LLONG_MAX
#define MOD 1000000009
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define gett(x,m) get<m>(x)
#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define sorta(a,sz) sort(a,a+sz)
#define inputar(a,b){\
    for(int i=0;i<b;i++){\
        cin >> a[i];\
    }\
}
#define inputvec(a,b){\
    for(int i=0;i<b;i++){\
        ll num;\
        cin >> num;\
        a.pb(num);\
    }\
}
#define outputar(a,b){\
    for(int i=0;i<b;i++){\
        cout << a[i] << " ";\
    }\
    cout << "\n";\
}
#define outputvec(a){\
    for(auto x:a){\
        cout << x << " ";\
    }\
    cout << "\n";\
}
#define reset(a,n,v){\
    for(int i=0;i<n;i++){\
        a[i]=v;\
    }\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef double db;
typedef long double ldb;
inline void USACO(string filename){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}
int valid(int n, int inputSeq[])
{
	map<int,int> b; 
	int x=-1; 
	for(int i=0;i<n;i++){
		if(inputSeq[i]<=n){
			x=i; 
		}
		b[inputSeq[i]]++; 
	}
	for(auto x:b){
		if(x.second>1){
			return 0;
		}
	}
	if(x==-1){
		return 1; 
	}
	vector<int> a; 
	a.resize(n); 
	int h1=inputSeq[x]-1; 
	for(int i=0;i<n;i++){
		a[x]=h1+1;
		x++;
		x%=n; 
		h1++; 
		h1%=n; 
	}
	for(int i=0;i<n;i++){
		if(inputSeq[i]<=n && inputSeq[i]!=a[i]){
			return 0;
		}
	}

	return 1; 
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	int ind=0;
	vector<pii> c; 
	c.pb(mp(n,-1)); 
	int x=-1; 
	for(int i=0;i<n;i++){
		if(gondolaSeq[i]>n){
			c.pb(mp(gondolaSeq[i],i)); 
		}
		else{
			x=i; 
		}
	}
	vector<int> a; 
	a.resize(n); 
	if(x!=-1){
		int h1=gondolaSeq[x]-1; 
		for(int i=0;i<n;i++){
			a[x]=h1+1;
			x++;
			x%=n; 
			h1++; 
			h1%=n; 
		}
	}
	else{
		for(int i=0;i<n;i++){
			a[i]=i+1; 
		}
	}
	sortv(c); 
	int sz=(int)c.size(); 
	for(int i=1;i<sz;i++){
		replacementSeq[ind]=a[c[i].ss];
		ind++; 
		for(int j=c[i-1].ff+1;j<c[i].ff;j++){
			replacementSeq[ind]=j;
			ind++; 
		}
	}
	return ind; 
}

//----------------------
ll powmod(ll x,ll y,ll md){
    if(y==0){
        return 1;
    }
    x%=md;
    if(x==0){
        return 0;
    }
    ll res=1;
    while(y>0){
        if(y%2){
            res*=x;
            res%=md;
        }
        y/=2;
        x*=x;
        x%=md;
    }
    return res;
}
int countReplacement(int n, int inputSeq[])
{
	if(valid(n,inputSeq)==0){
		return 0;
	}
	ll res=1; 
	vector<pii> c; 
	c.pb(mp(n,-1)); 
	int x=-1; 
	for(int i=0;i<n;i++){
		if(inputSeq[i]>n){
			c.pb(mp(inputSeq[i],i)); 
		}
		else{
			x=i;
		}
	}
	sortv(c); 
	int sz=(int)c.size(); 
	for(int i=1;i<sz;i++){
		res*=powmod(sz-i,c[i].ff-c[i-1].ff-1,MOD);
		res%=MOD;
	}
	if(x==-1){
		res*=(ll)n; 
		res%=MOD;
	}
	return (int)res; 
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	8 ms	2396 KB	Output is correct
7	Correct	21 ms	3736 KB	Output is correct
8	Correct	16 ms	4224 KB	Output is correct
9	Correct	5 ms	1624 KB	Output is correct
10	Correct	18 ms	4956 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	8 ms	2312 KB	Output is correct
7	Correct	20 ms	3588 KB	Output is correct
8	Correct	16 ms	4184 KB	Output is correct
9	Correct	5 ms	1628 KB	Output is correct
10	Correct	18 ms	4956 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	11 ms	2140 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	29 ms	4996 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	544 KB	Output is correct
2	Correct	344 KB	Output is correct
3	Correct	344 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	600 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	7 ms	860 KB	Output is correct
12	Correct	7 ms	1116 KB	Output is correct
13	Correct	11 ms	1308 KB	Output is correct
14	Correct	7 ms	860 KB	Output is correct
15	Correct	16 ms	2388 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct

Subtask #8
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	396 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct

Subtask #9
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	30 ms	4228 KB	Output is correct
10	Correct	23 ms	3672 KB	Output is correct
11	Correct	10 ms	1500 KB	Output is correct
12	Correct	13 ms	1884 KB	Output is correct
13	Correct	2 ms	604 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	30 ms	4444 KB	Output is correct
10	Correct	23 ms	3676 KB	Output is correct
11	Correct	9 ms	1628 KB	Output is correct
12	Correct	11 ms	1880 KB	Output is correct
13	Correct	2 ms	628 KB	Output is correct
14	Correct	37 ms	5468 KB	Output is correct
15	Correct	43 ms	6156 KB	Output is correct
16	Correct	7 ms	1368 KB	Output is correct
17	Correct	29 ms	4124 KB	Output is correct
18	Correct	14 ms	2652 KB	Output is correct

Submission #865827

Compilation message