Submission #85331

#	Time	Username	Problem	Language	Result	Execution time	Memory
85331		vex	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	3 ms	1000 KiB

bridge

#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;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37