Submission #1234703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234703		Hanksburger	Rotating Lines (APIO25_rotate)	C++20	16 / 100	54 ms	4208 KiB

rotate

#include "rotate.h"
#include <bits/stdc++.h>
using namespace std;
int cur[100005], target[100005], indx[100005], placed[100005], n;
vector<pair<int, int> > b, c;
void solve(int i)
{
    placed[i]=1;
    if (cur[i]==target[i])
        return;
    if (cur[i]>target[i])
    {
        vector<int> tmp;
        tmp.push_back(indx[i]);
        rotate(tmp, (target[i]-cur[i]+50000)%50000);
        return;
    }
    if (i<n/2*2-1 && cur[i+1]<target[i])
        solve(i+1);
    vector<int> tmp;
    tmp.push_back(indx[i]);
    rotate(tmp, (target[i]-cur[i]+50000)%50000);
}
void energy(int N, vector<int> a)
{
    int n=N, ind;
    for (int i=0; i<n; i++)
        b.push_back({a[i], i});
    sort(b.begin(), b.end());
    for (int i=0; i<n; i++)
    {
        if ((b[(i+n/2)%n].first-b[i].first+50000)%50000<=25000)
        {
            ind=i;
            break;
        }
    }
    for (int i=ind; i<ind+n; i++)
        c.push_back({(b[i%n].first-b[ind].first+50000)%50000, b[i%n].second});
    if (n&1)
    {
        vector<int> tmp;
        tmp.push_back(c[n-1].second);
        rotate(tmp, (c[0].first-c[n-1].first+50000)%50000);
    }
    for (int i=0; i<n/2; i++)
    {
        cur[i]=c[i+n/2].first;
        target[i]=(c[i].first+25000)%50000;
        indx[i]=c[i+n/2].second;
    }
    for (int i=0; i<n/2; i++)
        if (!placed[i])
            solve(i);
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 0 / 8
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 26