이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define maxn 1005
#define lg2 15
using namespace std;
int n;
int a[maxn];
int c[maxn][lg2];
int p[maxn];
int cn[maxn];
int pn[maxn];
int cnt[maxn];
void build();
int manji(int x,int y,int d);
int main()
{
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
build();
int m;
cin>>m;
for(int i=0;i<m;i++)
{
int x,y,d;
cin>>x>>y>>d;
cout<<manji(x,y,d)<<endl;
cout<<endl;
}
return 0;
}
void build()
{
for(int i=0;i<n;i++)cnt[a[i]]++;
for(int i=1;i<10;i++)cnt[i]+=cnt[i-1];
for(int i=0;i<n;i++)
{
cnt[a[i]]--;
p[cnt[a[i]]]=i;
}
int classes=1;
c[p[0]][0]=0;
for(int i=1;i<n;i++)
{
if(a[p[i-1]]!=a[p[i]])classes++;
c[p[i]][0]=classes-1;
}
for(int h=1;(1<<h)<=n;h++)
{
for(int i=0;i<n;i++)
{
pn[i]=p[i]-(1<<(h-1));
if(pn[i]<0)pn[i]+=n;
}
for(int i=0;i<n;i++)cnt[i]=0;
for(int i=0;i<n;i++)cnt[c[i][h-1]]++;
for(int i=1;i<classes;i++)cnt[i]+=cnt[i-1];
cout<<endl;
for(int i=0;i<n;i++)cout<<cnt[i]<<" ";
cout<<endl;
for(int i=0;i<n;i++)
{
cnt[c[pn[i]][h-1]]--;
p[cnt[c[pn[i]][h-1]]]=pn[i];
}
for(int i=0;i<n;i++)cout<<p[i]<<" ";
cout<<endl;
classes=1;
cn[p[0]]=0;
for(int i=1;i<n;i++)
{
pair<int,int>ff={c[p[i]][h-1],c[p[i]+(1<<(h-1))][h-1]};
pair<int,int>ss={c[p[i-1]][h-1],c[p[i-1]+(1<<(h-1))][h-1]};
if(ff!=ss)classes++;
cn[p[i]]=classes-1;
}
for(int i=0;i<n;i++)
{
c[p[i]][h]=cn[p[i]];
}
for(int i=0;i<n;i++)cout<<c[i][h]<<" ";
cout<<endl<<endl;
}
}
int manji(int x,int y,int d)
{
int t=int(log2(d));
pair<int,int> ff={c[x][t],c[(x+d-(1<<t)+n)%n][t]};
pair<int,int> ss={c[y][t],c[(y+d-(1<<t)+n)%n][t]};
if(ff<ss)return x;
return y;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |