Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2)

October 19, 2021By Simo CSS

Binary special session, which was also given a question by FST.

A. Sign in, the meaning of the question is, given a, b, c

f(0)=a, f(1)=b, f(n )=f(n-1)^f(n-2)

Find f(n)

A little simplification shows that f(x) is in accordance with a, b , A^b appears in the loop like this

Because a^b^a=b, a^b^b=a

Code:

#include 

#define int long long

#define sc(a) scanf("%lld",&a)

#define scc(a,b) scanf("%lld %lld",&a,&b)

#define sccc(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)

#define schar(a) scanf("%c",&a)

#define pr(a) printf("%lld",a)

#define fo(i,a,b) for(int i=a;i#define re(i,a,b) for(int i=a;i<=b;++i)

#define rfo(i,a,b) for(int i=a;i>b;--i)

#define rre(i,a,b) for(int i=a;i>=b;--i)

#define prn() printf("
")

#define prs() printf(" ")

#define mkp make_pair

#define pii pair

#define pub(a) push_back(a)

#define pob() pop_back()

#define puf(a) push_front(a)

#define pof() pop_front()

#define fst first

#define snd second

#define frt front()

#define bak back()

#define mem0(a) memset(a,0,sizeof(a))

#define memmx(a) memset(a,0x3f3f,sizeof(a))

#define memmn(a) memset(a,-0x3f3f,sizeof(a))

#define debug

#define db double

#define yyes cout<<"YES"<#define nno cout<<"NO"<using namespace std;

typedef vector<int> vei;

typedef vector vep;

typedef map<int,int> mpii;

typedef map<char,int> mpci;

typedef map<string,int> mpsi;

typedef deque<int> deqi;

typedef deque<char> deqc;

typedef priority_queue<int> mxpq;

typedef priority_queue<int,vector<int>, greater<int> > mnpq;

typedef priority_queue mxpqii;

typedef priority_queue,greater > mnpqii;

const int maxn=500005;

const int inf=0x3f3f3f3f3f3f3f3f;

const int MOD=100000007;

const db eps=1e-10;

int qpow(int a,int b){int tmp=a%MOD,ans=1;while(b){if(b&< span style="color: #800080;">1){ans*=tmp,ans%=MOD;}tmp*=tmp,tmp%=MOD,b>>=1;}return ans;}

int lowbit(int x){return x&-x;}

int max(int a,int b){return a>b?a :b;}

int min(int a,int b){return aa :b;}

int mmax(int a,int b,int c){return max(a,max(b,c));}

int mmin(int a,int b,int c){return min(a,min(b,c));}

void mod(int &a){a+=MOD ;a%=MOD;}

bool chk(int now){}

int half(int l,int r){while(l<=r){int m=(l+r)/2;if (chk(m))r=m-1;else l=m+1;}return l;}

int ll(int p){return p<<1;}

int rr(int p){return p<<1|1;}

int mm(int l,int r){return (l+r)/2;}

int lg(int x){if(x==0) return< /span> 1;return (int)log2(x)+1;}

bool smleql(db a,db b){if(areturn true; return false;}

db len(db a,db b,db c,db d){return sqrt((ac)*(ac) +(bd)*(b-d));}

bool isp(int x){if(x==1)return< /span> false;if(x==2)return true;for(int i=2; i*i<=x;++i)if(x%i==0)return false;return  true;}



int t,a,b,n;



signed main(){

 ios_base::sync_with_stdio(0);

 cin.tie(0),cout.tie(0);

 cin>>t;

 while(t--){

 cin>>a>>b>>n;

 if(n==0) cout<< a<<endl;

 else if(n==1) cout<endl;

 else{

 int k=n%3;

 if(k==0) cout<< a<<endl;

 else if(k==1) cout<endl;

 else cout<<(a^b)<<endl;

}

}

 return 0;

}

B. A question by FST, the question is to select a continuous interval of [l,r] and delete it, leaving the rest The numbers are different from each other. You don’t need to delete the output 0.

For the problem of continuous sub-segments, I went to the ruler method. Assuming that the interval of [l,r] is the interval I want to delete, in When determining l, keep reducing r to find the smallest interval.

At the beginning, I couldn’t pass pp. After thinking about it, I found that deleting the beginning and end of a continuous interval was not considered. I added it and judged pp.

After looking for a smaller hack for a long time, I finally found it:

8
1 2 3 4 2 6 5 4

Obviously, the 2, 4 in the fourth and fifth positions should be deleted, but I output 3, and I found [l,r] during debugging The interval does not traverse to the fourth and fifth positions at all.

Looking at the positive solution, it is found to be O(n^2logn), to the effect that after deleting a subinterval, only one prefix and one suffix are left, and their length can be 0

Then Enumeration does not have a prefix with repeated lengths, find the longest suffix without any repeated numbers, and use map to maintain it. Pay attention to the subscript details with empty prefixes and suffixes

Code:

< div class="code">

#include 

#define int long long

#define sc(a) scanf("%lld",&a)

#define scc(a,b) scanf("%lld %lld",&a,&b)

#define sccc(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)

#define schar(a) scanf("%c",&a)

#define pr(a) printf("%lld",a)

#define fo(i,a,b) for(int i=a;i#define re(i,a,b) for(int i=a;i<=b;++i)

#define rfo(i,a,b) for(int i=a;i>b;--i)

#define rre(i,a,b) for(int i=a;i>=b;--i)

#define prn() printf("
")

#define prs() printf(" ")

#define mkp make_pair

#define pii pair

#define pub(a) push_back(a)

#define pob() pop_back()

#define puf(a) push_front(a)

#define pof() pop_front()

#define fst first

#define snd second

#define frt front()

#define bak back()

#define mem0(a) memset(a,0,sizeof(a))

#define memmx(a) memset(a,0x3f3f,sizeof(a))

#define memmn(a) memset(a,-0x3f3f,sizeof(a))

#define debug

#define db double

#define yyes cout<<"YES"<#define nno cout<<"NO"<using namespace std;

typedef vector<int> vei;

typedef vector vep;

typedef map<int,int> mpii;

typedef map<char,int> mpci;

typedef map<string,int> mpsi;

typedef deque<int> deqi;

typedef deque<char> deqc;

typedef priority_queue<int> mxpq;

typedef priority_queue<int,vector<int>, greater<int> > mnpq;

typedef priority_queue mxpqii;

typedef priority_queue,greater > mnpqii;

const int maxn=500005;

const int inf=0x3f3f3f3f3f3f3f3f;

const int MOD=100000007;

const db eps=1e-10;

int qpow(int a,int b){int tmp=a%MOD,ans=1;while(b){if(b&< span style="color: #800080;">1){ans*=tmp,ans%=MOD;}tmp*=tmp,tmp%=MOD,b>>=1;}return ans;}

int lowbit(int x){return x&-x;}

int max(int a,int b){return a>b?a :b;}

int min(int a,int b){return aa :b;}

int mmax(int a,int b,int c){return max(a,max(b,c));}

int mmin(int a,int b,int c){return min(a,min(b,c));}

void mod(int &a){a+=MOD ;a%=MOD;}

bool chk(int now){}

int half(int l,int r){while(l<=r){int m=(l+r)/2;if (chk(m))r=m-1;else l=m+1;}return l;}

int ll(int p){return p<<1;}

int rr(int p){return p<<1|1;}

int mm(int l,int r){return (l+r)/2;}

int lg(int x){if(x==0) return< /span> 1;return (int)log2(x)+1;}

bool smleql(db a,db b){if(areturn true; return false;}

db len(db a,db b,db c,db d){return sqrt((ac)*(ac) +(bd)*(b-d));}

bool isp(int x){if(x==1)return< /span> false;if(x==2)return true;for(int i=2; i*i<=x;++i)if(x%i==0)return false;return  true;}



int n,a[maxn];

mpii mp;



signed main(){

 ios_base::sync_with_stdio(0);

 cin.tie(0),cout.tie(0);

 cin>>n;

 re(i,1,n) cin>>a[i ];

 int ans=n-1;

 re(i,1,n){

 bool can=1;

 mp.clear();

 re(j,1,i-1< span style="color: #000000;">){

 mp[a[j]]++;

 if(mp[a[j]]==2){

 can=0;

 break;

}

}

 int p=n+1;

 rre(j,n,i){

 mp[a[j]]++;

 if(mp[a[j]]==1) p=j;

 else break;

}

 if(can) ans=min(ans,p-i) ;

}

 cout<<ans;

 return 0;

}

/*

6

2 2 3 3 4 2

8

1 2 3 4 2 6 5 4

10

7 6 5 4 3 2 1 7 7 7

*/

C, given an n, ensure that n is a multiple of 4 , Construct an n*n matrix, so that each number in [0,n^2-1] appears only once, and the XOR sum of each row and column of the matrix is the same

Guess the conclusion first , The exclusive or sum of ranks is 0

During the competition, the solution given by ly was four or four groups. I didn’t understand it too much. After the competition, I discussed it with zyf for a long time and finally figured it out.

First of all, find a 4*4 matrix that satisfies the conditions. I used the following:

This is a practical use of the following conclusion, in PS.

0 1 2 3

4 5 6 7

8 9 9 10 11

12 13 14 15

Consider something like this:

a^b=(a +c)^(b+c)What are the conditions?

The answer is c>a&&c>b

In fact, if c>a, then a+c will only be in the binary digit where a is 0 Make changes, and the XOR sum will become 0 after an even number of XORs

For example: a^a=0, a^a^a^a=0 p>

So keep repeating the 4*4 matrix, adding 16, 32, 48 each time

The get function below is used to obtain a certain The number of points is similar to a matrix with n rows and n columns. A[i][j] has a total of i*n+j elements (i, j start from 0).

True data structure The final exam.

Code:

#include 

#define int long long

#define sc(a) scanf("%lld",&a)

#define scc(a,b) scanf("%lld %lld",&a,&b)

#define sccc(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)

#define schar(a) scanf("%c",&a)

#define pr(a) printf("%lld",a)

#define fo(i,a,b) for(int i=a;i#define re(i,a,b) for(int i=a;i<=b;++i)

#define rfo(i,a,b) for(int i=a;i>b;--i)

#define rre(i,a,b) for(int i=a;i>=b;--i)

#define prn() printf("
")

#define prs() printf(" ")

#define mkp make_pair

#define pii pair

#define pub(a) push_back(a)

#define pob() pop_back()

#define puf(a) push_front(a)

#define pof() pop_front()

#define fst first

#define snd second

#define frt front()

#define bak back()

#define mem0(a) memset(a,0,sizeof(a))

#define memmx(a) memset(a,0x3f3f,sizeof(a))

#define memmn(a) memset(a,-0x3f3f,sizeof(a))

#define debug

#define db double

#define yyes cout<<"YES"<#define nno cout<<"NO"<using namespace std;

typedef vector<int> vei;

typedef vector vep;

typedef map<int,int> mpii;

typedef map<char,int> mpci;

typedef map<string,int> mpsi;

typedef deque<int> deqi;

typedef deque<char> deqc;

typedef priority_queue<int> mxpq;

typedef priority_queue<int,vector<int>, greater<int> > mnpq;

typedef priority_queue mxpqii;

typedef priority_queue,greater > mnpqii;

const int maxn=500005;

const int inf=0x3f3f3f3f3f3f3f3f;

const int MOD=100000007;

const db eps=1e-10;

int qpow(int a,int b){int tmp=a%MOD,ans=1;while(b){if(b&< span style="color: #800080;">1){ans*=tmp,ans%=MOD;}tmp*=tmp,tmp%=MOD,b>>=1;}return ans;}

int lowbit(int x){return x&-x;}

int max(int a,int b){return a>b?a :b;}

int min(int a,int b){return aa :b;}

int mmax(int a,int b,int c){return max(a,max(b,c));}

int mmin(int a,int b,int c){return min(a,min(b,c));}

void mod(int &a){a+=MOD ;a%=MOD;}

bool chk(int now){}

int half(int l,int r){while(l<=r){int m=(l+r)/2;if (chk(m))r=m-1;else l=m+1;}return l;}

int ll(int p){return p<<1;}

int rr(int p){return p<<1|1;}

int mm(int l,int r){return (l+r)/2;}

int lg(int x){if(x==0) return< /span> 1;return (int)log2(x)+1;}

bool smleql(db a,db b){if(areturn true; return false;}

db len(db a,db b,db c,db d){return sqrt((ac)*(ac) +(bd)*(b-d));}

bool isp(int x){if(x==1)return< /span> false;if(x==2)return true;for(int i=2; i*i<=x;++i)if(x%i==0)return false;return  true;}



int n;

int ans[1005][1005];

int a[4][4]={0,1,2,3, 4,5,6,7,8,9,10,11,12, 13,14,15< /span>};



void out(){

 fo(i,0,n){

 fo(j,0,n){

 cout<' ' ;

}

 cout<<endl;

}

}



int get(int i,int j){

 return (n/4)*(i/ 4)+(j/4);

}



void solve(){

 fo(i,0,n){

 fo(j,0,n){

 ans[i][j]=get(i,j)*16+a[i%4][j%4< span style="color: #000000;">];

}

}

}



signed main(){

 ios_base::sync_with_stdio(0);

 cin.tie(0),cout.tie(0);

 cin>>n;

 solve();

 out();

 return 0;

}

PS: I learned a conclusion from here, the XOR sum of 4 consecutive numbers starting with a multiple of 4 is 0 strong>

Such as 0, 1, 2, 3 and 8, 9, 10, 11

D, suppose here There is a permutation of n, the number at each position is pi, and si represents the sum of all numbers smaller than pi before i

Now given n and si, you need to reconstruct pi to ensure that there is a solution

First consider the position of 1, suppose there is such an arrangement:

3 2 5 1 4

Its si array is easy to find:

0 0 0 5 0 6

First of all, for 1, the si at its corresponding position must be 0, because there will be no numbers smaller than 1, and for all the numbers after 1 For numbers, their si must not be 0, which means that the position of the last 0 must be 1

In the above example, the position of 1 is found first, and pi is reconstructed:

* * * * 1 *

Then set the si at position 1 to infinity, and reduce all si after position 1 by 1. This step can be maintained by a line segment tree, as shown in the figure:

p>

0 0 0 5 inf 5

At this time, look for the position of 2. Obviously, after 1 disappears, 2 becomes the smallest number. At this time, the position of the last 0 is the position of 2. , Repeat the above operation.

pi: * 2 * 1 *

si: 0 inf 3 inf-2 3

The algorithm is very clear here, and it is maintained by the line segment tree The value of si is filled with numbers from 1 to n back.

The following question is how to find the position of the last 0 in logn, and use the line segment tree to search downwards in two ways. Each time, first check whether the minimum value on the right side is 0. If not, search to the left. In this way, the position of the 0 to the far right must be found.

When writing, I downloaded the tag and wrote the pot. I actually only download it when the tag is equal to 0. I will use it sparingly in the future! A is used to judge whether a is equal to 0, and more use==

Code:

#include
#define int long long
#define sc(a) scanf("%lld",&a)
#define scc(a,b) scanf("%lld %lld",&a,&b)
#define sccc(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define schar(a) scanf("%c",&a)
#define pr(a) printf("%lld",a)
#define fo(i,a,b) for(int i=a;i#define re(i,a,b) for(int i=a;i<=b;++i)
#define rfo(i,a,b) for(int i=a;i>b;--i)
#define rre(i,a,b) for(int i=a;i>=b;--i)
#define prn() printf(" ")
#define prs() printf(" ")
#define mkp make_pair
#define pii pair
#define pub(a) push_back(a)
#define pob() pop_back()
#define puf(a) push_front(a)
#define pof() pop_front()
#define fst first
#define snd second
#define frt front()
#define bak back()
#define mem0(a) memset(a,0,sizeof(a))
#define memmx(a) memset(a,0x3f3f,sizeof(a))
#define memmn(a) memset(a,-0x3f3f,sizeof(a))
#define debug
#define db double
#define yyes cout<<"YES"<#define nno cout<<"NO"<using namespace std;
typedef vector<int> vei;
typedef vector vep;
typedef map<int,int> mpii;
typedef map<char,int> mpci;
typedef map<string,int> mpsi;
typedef deque<int> deqi;
typedef deque<char> deqc;
typedef priority_queue<int> mxpq;
typedef priority_queue<int,vector<int>, greater<int> > mnpq;
typedef priority_queue mxpqii;
typedef priority_queue,greater > mnpqii;
const int maxn=1000005;
const int inf=0x3f3f3f3f3f3f3f3f;
const int MOD=100000007;
const db eps=1e-10;
int qpow(int a,int b){int tmp=a%MOD,ans=1;while(b){if(b&1){ans*=tmp,ans%=MOD;}tmp*=tmp,tmp%=MOD,b>>=1;}return ans;}
int lowbit(int x){return x&-x;}
int max(int a,int b){return a>b?a :b;}
int min(int a,int b){return aa :b;}
int mmax(int a,int b,int c){return max(a,max(b,c));}
int mmin(int a,int b,int c){return min(a,min(b,c));}
void mod(int &a){a+=MOD ;a%=MOD;}
bool chk(int now){}
int half(int l,int r){while(l<=r){int m=(l+r)/2;if (chk(m))r=m-1;else l=m+1;}return l;}
int ll(int p){return p<<1;}
int rr(int p){return p<<1|1;}
int mm(int l,int r){return (l+r)/2;}
int lg(int x){if(x==0) return 1;return (int)log2(x)+1;}
bool smleql(db a,db b){if(areturn true; return false;}
db len(db a,db b,db c,db d){return sqrt((ac)*(ac) +(bd)*(b-d));}
bool isp(int x){if(x==1)return false;if(x==2)return true;for(int i=2; i*i<=x;++i)if(x%i==0)return false;return true;}

int n,s[maxn],ans[maxn];
int tr[maxn],tag[maxn];

void up(int p){tr[p ]=min(tr[ll(p)],tr[rr(p)]);}
void down(int p){
if(tag[p]){
tr[ll(p)]+=tag[p];
tr[rr(p)]+=tag[p];
tag[ll(p)]+=tag[p];
tag[rr(p)]+=tag[p];
tag[p]=0;
}
}

void build(int p,int l,int r){
if(l==r){
tr[p]=s[l];
return;
}
int m=mm(l,r);
build(ll(p),l,m);
build(rr(p),m+1,r);
up(p);
}

int q(int p,int l,int r,int pos){
if(l==r&&l==pos)
return tr[p];
int m=mm(l,r);
down(p);
int ans;
if(pos<=m) ans=q(ll(p ),l,m,pos);
else ans=q(rr(p),m+1,r,pos);
up(p);
return ans;
}

void change(int p,int l,int r,int L,int R,int v){
if(L<=l&&r<=R){
tr[p]+=v;
tag[p]+=v;
return;
}
int m=mm(l,r);
down(p);
if(L<=m) change(ll(p), l,m,L,R,v);
if(R>m) change(rr(p),m+ 1,r,L,R,v);
up(p);
}

int pos(int p,int l,int r){
if(l==r) return l;
int res=-1;
int m=mm(l,r);
down(p);
if(tr[rr(p)]==0)
res=pos(rr(p),m+1,r) ;
else
res=pos(ll(p),l,m);
up(p);
return res;
}

signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
re(i,1,n) cin>>s[i ];
memmx(tr);
build(1,1,n);
re(i,1,n){
int p=pos(1,1,n);
// re(j,1,n) cout<
ans[p]=i;
if(p!=n) change(1 ,1,n,p+1,n,-i);
change(1,1,n,p,p,inf);
}
re(i,1,n) cout<' ';
return 0;
}
/*
5
0 1 1 1 10
*/

#include
#define int long long
#define sc(a) scanf("%lld",&a)
#define scc(a,b) scanf("%lld %lld",&a,&b)
#define sccc(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define schar(a) scanf("%c",&a)
#define pr(a) printf("%lld",a)
#define fo(i,a,b) for(int i=a;i#define re(i,a,b) for(int i=a;i<=b;++i)
#define rfo(i,a,b) for(int i=a;i>b;--i)
#define rre(i,a,b) for(int i=a;i>=b;--i)
#define prn() printf(" ")
#define prs() printf(" ")
#define mkp make_pair
#define pii pair
#define pub(a) push_back(a)
#define pob() pop_back()
#define puf(a) push_front(a)
#define pof() pop_front()
#define fst first
#define snd second
#define frt front()
#define bak back()
#define mem0(a) memset(a,0,sizeof(a))
#define memmx(a) memset(a,0x3f3f,sizeof(a))
#define memmn(a) memset(a,-0x3f3f,sizeof(a))
#define debug
#define db double
#define yyes cout<<"YES"<#define nno cout<<"NO"<using namespace std;
typedef vector<int> vei;
typedef vector vep;
typedef map<int,int> mpii;
typedef map<char,int> mpci;
typedef map<string,int> mpsi;
typedef deque<int> deqi;
typedef deque<char> deqc;
typedef priority_queue<int> mxpq;
typedef priority_queue<int,vector<int>, greater<int> > mnpq;
typedef priority_queue mxpqii;
typedef priority_queue,greater > mnpqii;
const int maxn=500005;
const int inf=0x3f3f3f3f3f3f3f3f;
const int MOD=100000007;
const db eps=1e-10;
int qpow(int a,int b){int tmp=a%MOD,ans=1;while(b){if(b&1){ans*=tmp,ans%=MOD;}tmp*=tmp,tmp%=MOD,b>>=1;}return ans;}
int lowbit(int x){return x&-x;}
int max(int a,int b){return a>b?a :b;}
int min(int a,int b){return aa :b;}
int mmax(int a,int b,int c){return max(a,max(b,c));}
int mmin(int a,int b,int c){return min(a,min(b,c));}
void mod(int &a){a+=MOD ;a%=MOD;}
bool chk(int now){}
int half(int l,int r){while(l<=r){int m=(l+r)/2;if (chk(m))r=m-1;else l=m+1;}return l;}
int ll(int p){return p<<1;}
int rr(int p){return p<<1|1;}
int mm(int l,int r){return (l+r)/2;}
int lg(int x){if(x==0) return 1;return (int)log2(x)+1;}
bool smleql(db a,db b){if(areturn true; return false;}
db len(db a,db b,db c,db d){return sqrt((ac)*(ac) +(bd)*(b-d));}
bool isp(int x){if(x==1)return false;if(x==2)return true;for(int i=2; i*i<=x;++i)if(x%i==0)return false;return true;}

int t,a,b,n;

signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--){
cin>>a>>b>>n;
if(n==0) cout<< a<<endl;
else if(n==1) cout<endl;
else{
int k=n%3;
if(k==0) cout<< a<<endl;
else if(k==1) cout<endl;
else cout<<(a^b)<<endl;
}
}
return 0;
}

#include
#define int long long
#define sc(a) scanf("%lld",&a)
#define scc(a,b) scanf("%lld %lld",&a,&b)
#define sccc(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define schar(a) scanf("%c",&a)
#define pr(a) printf("%lld",a)
#define fo(i,a,b) for(int i=a;i#define re(i,a,b) for(int i=a;i<=b;++i)
#define rfo(i,a,b) for(int i=a;i>b;--i)
#define rre(i,a,b) for(int i=a;i>=b;--i)
#define prn() printf(" ")
#define prs() printf(" ")
#define mkp make_pair
#define pii pair
#define pub(a) push_back(a)
#define pob() pop_back()
#define puf(a) push_front(a)
#define pof() pop_front()
#define fst first
#define snd second
#define frt front()
#define bak back()
#define mem0(a) memset(a,0,sizeof(a))
#define memmx(a) memset(a,0x3f3f,sizeof(a))
#define memmn(a) memset(a,-0x3f3f,sizeof(a))
#define debug
#define db double
#define yyes cout<<"YES"<#define nno cout<<"NO"<using namespace std;
typedef vector<int> vei;
typedef vector vep;
typedef map<int,int> mpii;
typedef map<char,int> mpci;
typedef map<string,int> mpsi;
typedef deque<int> deqi;
typedef deque<char> deqc;
typedef priority_queue<int> mxpq;
typedef priority_queue<int,vector<int>, greater<int> > mnpq;
typedef priority_queue mxpqii;
typedef priority_queue,greater > mnpqii;
const int maxn=500005;
const int inf=0x3f3f3f3f3f3f3f3f;
const int MOD=100000007;
const db eps=1e-10;
int qpow(int a,int b){int tmp=a%MOD,ans=1;while(b){if(b&1){ans*=tmp,ans%=MOD;}tmp*=tmp,tmp%=MOD,b>>=1;}return ans;}
int lowbit(int x){return x&-x;}
int max(int a,int b){return a>b?a :b;}
int min(int a,int b){return aa :b;}
int mmax(int a,int b,int c){return max(a,max(b,c));}
int mmin(int a,int b,int c){return min(a,min(b,c));}
void mod(int &a){a+=MOD ;a%=MOD;}
bool chk(int now){}
int half(int l,int r){while(l<=r){int m=(l+r)/2;if (chk(m))r=m-1;else l=m+1;}return l;}
int ll(int p){return p<<1;}
int rr(int p){return p<<1|1;}
int mm(int l,int r){return (l+r)/2;}
int lg(int x){if(x==0) return 1;return (int)log2(x)+1;}
bool smleql(db a,db b){if(areturn true; return false;}
db len(db a,db b,db c,db d){return sqrt((ac)*(ac) +(bd)*(b-d));}
bool isp(int x){if(x==1)return false;if(x==2)return true;for(int i=2; i*i<=x;++i)if(x%i==0)return false;return true;}

int n,a[maxn];
mpii mp;

signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
re(i,1,n) cin>>a[i ];
int ans=n-1;
re(i,1,n){
bool can=1;
mp.clear();
re(j,1,i-1){
mp[a[j]]++;
if(mp[a[j]]==2){
can=0;
break;
}
}
int p=n+1;
rre(j,n,i){
mp[a[j]]++;
if(mp[a[j]]==1) p=j;
else break;
}
if(can) ans=min(ans,p-i) ;
}
cout<<ans;
return 0;
}
/*
6
2 2 3 3 4 2
8
1 2 3 4 2 6 5 4
10
7 6 5 4 3 2 1 7 7 7
*/

#include
#define int long long
#define sc(a) scanf("%lld",&a)
#define scc(a,b) scanf("%lld %lld",&a,&b)
#define sccc(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define schar(a) scanf("%c",&a)
#define pr(a) printf("%lld",a)
#define fo(i,a,b) for(int i=a;i#define re(i,a,b) for(int i=a;i<=b;++i)
#define rfo(i,a,b) for(int i=a;i>b;--i)
#define rre(i,a,b) for(int i=a;i>=b;--i)
#define prn() printf(" ")
#define prs() printf(" ")
#define mkp make_pair
#define pii pair
#define pub(a) push_back(a)
#define pob() pop_back()
#define puf(a) push_front(a)
#define pof() pop_front()
#define fst first
#define snd second
#define frt front()
#define bak back()
#define mem0(a) memset(a,0,sizeof(a))
#define memmx(a) memset(a,0x3f3f,sizeof(a))
#define memmn(a) memset(a,-0x3f3f,sizeof(a))
#define debug
#define db double
#define yyes cout<<"YES"<#define nno cout<<"NO"<using namespace std;
typedef vector<int> vei;
typedef vector vep;
typedef map<int,int> mpii;
typedef map<char,int> mpci;
typedef map<string,int> mpsi;
typedef deque<int> deqi;
typedef deque<char> deqc;
typedef priority_queue<int> mxpq;
typedef priority_queue<int,vector<int>, greater<int> > mnpq;
typedef priority_queue mxpqii;
typedef priority_queue,greater > mnpqii;
const int maxn=500005;
const int inf=0x3f3f3f3f3f3f3f3f;
const int MOD=100000007;
const db eps=1e-10;
int qpow(int a,int b){int tmp=a%MOD,ans=1;while(b){if(b&1){ans*=tmp,ans%=MOD;}tmp*=tmp,tmp%=MOD,b>>=1;}return ans;}
int lowbit(int x){return x&-x;}
int max(int a,int b){return a>b?a :b;}
int min(int a,int b){return aa :b;}
int mmax(int a,int b,int c){return max(a,max(b,c));}
int mmin(int a,int b,int c){return min(a,min(b,c));}
void mod(int &a){a+=MOD ;a%=MOD;}
bool chk(int now){}
int half(int l,int r){while(l<=r){int m=(l+r)/2;if (chk(m))r=m-1;else l=m+1;}return l;}
int ll(int p){return p<<1;}
int rr(int p){return p<<1|1;}
int mm(int l,int r){return (l+r)/2;}
int lg(int x){if(x==0) return 1;return (int)log2(x)+1;}
bool smleql(db a,db b){if(areturn true; return false;}
db len(db a,db b,db c,db d){return sqrt((ac)*(ac) +(bd)*(b-d));}
bool isp(int x){if(x==1)return false;if(x==2)return true;for(int i=2; i*i<=x;++i)if(x%i==0)return false;return true;}

int n;
int ans[1005][1005];
int a[4][4]={0,1,2,3, 4,5,6,7,8,9,10,11,12, 13,14,15};

void out(){
fo(i,0,n){
fo(j,0,n){
cout<' ' ;
}
cout<<endl;
}
}

int get(int i,int j){
return (n/4)*(i/ 4)+(j/4);
}

void solve(){
fo(i,0,n){
fo(j,0,n){
ans[i][j]=get(i,j)*16+a[i%4][j%4];
}
}
}

signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
solve();
out();
return 0;
}

#include
#define int long long
#define sc(a) scanf("%lld",&a)
#define scc(a,b) scanf("%lld %lld",&a,&b)
#define sccc(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define schar(a) scanf("%c",&a)
#define pr(a) printf("%lld",a)
#define fo(i,a,b) for(int i=a;i#define re(i,a,b) for(int i=a;i<=b;++i)
#define rfo(i,a,b) for(int i=a;i>b;--i)
#define rre(i,a,b) for(int i=a;i>=b;--i)
#define prn() printf(" ")
#define prs() printf(" ")
#define mkp make_pair
#define pii pair
#define pub(a) push_back(a)
#define pob() pop_back()
#define puf(a) push_front(a)
#define pof() pop_front()
#define fst first
#define snd second
#define frt front()
#define bak back()
#define mem0(a) memset(a,0,sizeof(a))
#define memmx(a) memset(a,0x3f3f,sizeof(a))
#define memmn(a) memset(a,-0x3f3f,sizeof(a))
#define debug
#define db double
#define yyes cout<<"YES"<#define nno cout<<"NO"<using namespace std;
typedef vector<int> vei;
typedef vector vep;
typedef map<int,int> mpii;
typedef map<char,int> mpci;
typedef map<string,int> mpsi;
typedef deque<int> deqi;
typedef deque<char> deqc;
typedef priority_queue<int> mxpq;
typedef priority_queue<int,vector<int>, greater<int> > mnpq;
typedef priority_queue mxpqii;
typedef priority_queue,greater > mnpqii;
const int maxn=1000005;
const int inf=0x3f3f3f3f3f3f3f3f;
const int MOD=100000007;
const db eps=1e-10;
int qpow(int a,int b){int tmp=a%MOD,ans=1;while(b){if(b&1){ans*=tmp,ans%=MOD;}tmp*=tmp,tmp%=MOD,b>>=1;}return ans;}
int lowbit(int x){return x&-x;}
int max(int a,int b){return a>b?a :b;}
int min(int a,int b){return aa :b;}
int mmax(int a,int b,int c){return max(a,max(b,c));}
int mmin(int a,int b,int c){return min(a,min(b,c));}
void mod(int &a){a+=MOD ;a%=MOD;}
bool chk(int now){}
int half(int l,int r){while(l<=r){int m=(l+r)/2;if (chk(m))r=m-1;else l=m+1;}return l;}
int ll(int p){return p<<1;}
int rr(int p){return p<<1|1;}
int mm(int l,int r){return (l+r)/2;}
int lg(int x){if(x==0) return 1;return (int)log2(x)+1;}
bool smleql(db a,db b){if(areturn true; return false;}
db len(db a,db b,db c,db d){return sqrt((ac)*(ac) +(bd)*(b-d));}
bool isp(int x){if(x==1)return false;if(x==2)return true;for(int i=2; i*i<=x;++i)if(x%i==0)return false;return true;}

int n,s[maxn],ans[maxn];
int tr[maxn],tag[maxn];

void up(int p){tr[p ]=min(tr[ll(p)],tr[rr(p)]);}
void down(int p){
if(tag[p]){
tr[ll(p)]+=tag[p];
tr[rr(p)]+=tag[p];
tag[ll(p)]+=tag[p];
tag[rr(p)]+=tag[p];
tag[p]=0;
}
}

void build(int p,int l,int r){
if(l==r){
tr[p]=s[l];
return;
}
int m=mm(l,r);
build(ll(p),l,m);
build(rr(p),m+1,r);
up(p);
}

int q(int p,int l,int r,int pos){
if(l==r&&l==pos)
return tr[p];
int m=mm(l,r);
down(p);
int ans;
if(pos<=m) ans=q(ll(p ),l,m,pos);
else ans=q(rr(p),m+1,r,pos);
up(p);
return ans;
}

void change(int p,int l,int r,int L,int R,int v){
if(L<=l&&r<=R){
tr[p]+=v;
tag[p]+=v;
return;
}
int m=mm(l,r);
down(p);
if(L<=m) change(ll(p), l,m,L,R,v);
if(R>m) change(rr(p),m+ 1,r,L,R,v);
up(p);
}

int pos(int p,int l,int r){
if(l==r) return l;
int res=-1;
int m=mm(l,r);
down(p);
if(tr[rr(p)]==0)
res=pos(rr(p),m+1,r) ;
else
res=pos(ll(p),l,m);
up(p);
return res;
}

signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
re(i,1,n) cin>>s[i ];
memmx(tr);
build(1,1,n);
re(i,1,n){
int p=pos(1,1,n);
// re(j,1,n) cout<
ans[p]=i;
if(p!=n) change(1 ,1,n,p+1,n,-i);
change(1,1,n,p,p,inf);
}
re(i,1,n) cout<' ';
return 0;
}
/*
5
0 1 1 1 10
*/

Leave a Comment Cancel reply