#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;
}
# |
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 |
# |
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 |
# |
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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
544 KB |
Output is correct |
2 |
Correct |
0 ms |
344 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 |
# |
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 |
# |
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 |
# |
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 |
# |
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 |
# |
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 |
# |
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 |