Submission #1177115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177115		vnedu	Space Pirate (JOI14_space_pirate)	C++20	80 / 100	185 ms	71756 KiB

space_pirate

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int N = 1e5 + 15;
int n,a[N];
ll k;
namespace sub1
{
    bool check()
    {
        return (n<=100);
    }
    const int N = 102;
    int cnt[N],b[N],ptr,trace[N];
    void work()
    {
        int cur=1;
        b[ptr=1]=cur;
        trace[cur]=1;
        memset(trace,0,sizeof(trace));

        for (int tri=1; tri<=k; ++tri)
        {
            int gogo=a[cur];
            int lst=trace[gogo];
            if (lst==0)
            {
                b[++ptr]=gogo;
                cur=gogo;
                trace[cur]=ptr;
            }
            else
            {
                ll need=k-tri;
                int sz=ptr-lst+1;
                need%=sz;
                ptr=lst+need;
                break;
            }
        }
        ++cnt[b[ptr]];
    }
    void solve()
    {
        for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j)
        {
            int old=a[i];
            a[i]=j;
            work();
            a[i]=old;
        }
        for (int i=1; i<=n; ++i) cout<<cnt[i]<<'\n';
    }
}
namespace sub2
{
    bool check()
    {
        return (n<=3000);
    }
    const int N = 3e3 + 33;
    int p[N][N],ptr[N],trace[N],lst[N],cnt[N],pos[N][N];
    int go(int i, ll k)
    {
        if (k<=ptr[i]-1)
        {
            return p[i][k+1];
        }
        k-=ptr[i];
        int cur=trace[i];
        k%=(ptr[i]-cur+1);
        return p[i][cur+k];
    }
    void solve()
    {
        for (int i=1; i<=n; ++i)
        {
            memset(lst,0,sizeof(lst));
            p[i][ptr[i]=1]=i;
            lst[i]=1;
            pos[i][i]=1;
//            continue;
            int cur=i;
            while (1)
            {
                int nxt=a[cur];
                if (lst[nxt])
                {
                    trace[i]=lst[nxt];
                    break;
                }
                p[i][++ptr[i]]=nxt;
                lst[nxt]=ptr[i];
                cur=nxt;
                pos[i][cur]=ptr[i];
            }
        }
//        for (int i=1; i<=n; ++i)
//        {
//            cout<<trace[i]<<"   ";
//            for (int j=1; j<=ptr[i]; ++j) cout<<p[i][j]<<' ';
//            cout<<'\n';
//        }
        int xxx=go(1,k);
        cnt[xxx]+=(n-ptr[1])*n;
        for (int tri=1; tri<=ptr[1]; ++tri) for (int b=1; b<=n; ++b)
        {
            ll nk=k-(tri-1);
            if (nk<=0)
            {
                ++cnt[xxx];
                continue;
            }
            int cur=p[1][tri];
            if (pos[b][cur]==0) ++cnt[go(b,nk-1)];
            else
            {
                int x=pos[b][cur];
                --nk;
                int sz=x;
                nk%=sz;
                ++cnt[p[b][1+nk]];
            }
        }
        for (int i=1; i<=n; ++i) cout<<cnt[i]<<'\n';
    }
}
namespace sub3
{
    int b[N];
    bool check()
    {
        for (int i=1; i<=n; ++i) b[i]=a[i];
        sort(b+1,b+1+n);
        for (int i=1; i<n; ++i) if (b[i]==b[i+1]) return 0;
        return 1;
    }
    vector<int> v;
    int p[N],m;
    bool is[N];
    ll cnt[N];
    void solve()
    {
        int cur=1;
        v.pb(cur);
        is[cur]=1;
        cur=a[cur];
        while (cur!=1)
        {
            v.pb(cur);
            is[cur]=1;
            cur=a[cur];
        }
//        for (int x : v) cout<<x<<' ';
//        return;
        m=(int)v.size();
        int xxx=v[k%m];
        cnt[xxx]+=(n-m)*1LL*n;
//        cout<<xxx<<' '<<cnt[xxx]<<'\n';
        int nonsense=0;
        for (int i=0; i<m; ++i)
        {
            if (i+1<=k) ++nonsense;
            else cnt[xxx]+=n-m;
        }
        for (int i=1; i<=n; ++i) if (!is[i]) cnt[i]+=nonsense;
//        return;
        for (int x=0; x<=m-2; ++x)
        {
            int r=k%(m-x);
            p[r]+=max(0,m-1-(x+1)-r+1);
            p[r+x]+=min(r,m-(x+1));
        }
//        for (int i=0; i<m; ++i) cout<<p[i]<<' ';
//        cout<<'\n';
//        return;
        for (int s=1; s<=m; ++s)
        {
            int lim=min(k,m-s*1LL),lst=-1;
//            cout<<lim<<'\n';
            cnt[xxx]+=max(0LL,m-s-k);
            for (int j=k%s; j<=lim; j+=s)
            {
                p[j]+=j-lst;
                lst=j;
            }
            if (lst<lim)
            {
//                cout<<"DSAD";
                p[lim+(k-lim)%s]+=lim-lst;
            }
        }
        for (int i=0; i<m; ++i) cnt[v[i]]+=p[i];
        for (int i=1; i<=n; ++i) cout<<cnt[i]<<'\n';
    }
}
void solve()
{
    cin>>n>>k;
    for (int i=1; i<=n; ++i) cin>>a[i];
    if (sub1::check()) return void(sub1::solve());
    if (sub2::check()) return void(sub2::solve());
    if (sub3::check()) return void(sub3::solve());
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    int testcase=1;
//    cin>>testcase;

    while (testcase--)
        solve();

//    #define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
//    cerr << "Time elapsed: " << TIME << " s.\n";
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 37 / 37
• Subtask 3: 33 / 33
• Subtask 4: 0 / 20