oj.uz

Submission #271885

# Submission time Handle Problem Language Result Execution time Memory
271885 2020-08-18T07:54:10 Z 최은수(#5096) Archery (IOI09_archery) C++17
69 / 100
 2000 ms 6140 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
bool chk[200010];
int pa[200010];
int n;
int par(int x)
{
    if(!chk[x])
        return x;
    return pa[x]=par(pa[x]);
}
inline void put(int x)
{
    chk[x]=1;
    pa[x]=x==1?n:x-1;
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int r;
    cin>>n>>r;
    r=(r-n*2)%n+n*2;
    int s;
    cin>>s;
    if(s==1)
        return cout<<n<<endl,0;
    vector<int>p(n*2-1);
    for(int&t:p)
        cin>>t;
    if(n<=400)
    {
        int mx=inf,mi=-1;
        for(int i=n;i>0;i--)
        {
            vector<pi>v(n+1);
            for(int j=1;j<i;j++)
                v[j]=pi(p[j*2-2],p[j*2-1]);
            v[i]=pi(s,p[i*2-2]);
            for(int j=i;j++<n;)
                v[j]=pi(p[j*2-3],p[j*2-2]);
            for(int j=0;j<r;j++)
            {
                for(int k=1;k++<n;)
                    if(v[k].fi<v[k].se)
                        swap(v[k].fi,v[k].se);
                if(v[1].fi>v[1].se)
                    swap(v[1].fi,v[1].se);
                for(int k=0;k<n;k++)
                    v[k].se=v[k+1].se;
                v[n].se=v[0].se;
            }
            int id=-1;
            for(int j=0;j++<n;)
                if(v[j].fi==s||v[j].se==s)
                    id=j;
            if(id<mx)
                mx=id,mi=i;
        }
        cout<<mi<<endl;
        return 0;
    }
    if(s<n+2)
    {
        if(n>13000)
            return cout<<n<<endl,0;
        int mx=inf,mi=-1;
        for(int i=n;i>max(0,n-330000000/n/n);i--)
        {
            vector<pi>v(n+1);
            for(int j=1;j<i;j++)
                v[j]=pi(p[j*2-2],p[j*2-1]);
            v[i]=pi(s,p[i*2-2]);
            for(int j=i;j++<n;)
                v[j]=pi(p[j*2-3],p[j*2-2]);
            for(int j=0;j<r;j++)
            {
                for(int k=1;k++<n;)
                    if(v[k].fi<v[k].se)
                        swap(v[k].fi,v[k].se);
                if(v[1].fi>v[1].se)
                    swap(v[1].fi,v[1].se);
                for(int k=0;k<n;k++)
                    v[k].se=v[k+1].se;
                v[n].se=v[0].se;
            }
            int id=-1;
            for(int j=0;j++<n;)
                if(v[j].fi==s||v[j].se==s)
                    id=j;
            if(id<mx)
                mx=id,mi=i;
        }
        cout<<mi<<endl;
        return 0;
    }
    int mx=inf,mi=-1;
    int ps=-1;
    {
        int i=n;
        vector<pi>v(n+1);
        for(int j=1;j<i;j++)
            v[j]=pi(p[j*2-2],p[j*2-1]);
        v[i]=pi(s,p[i*2-2]);
        for(int j=i;j++<n;)
            v[j]=pi(p[j*2-3],p[j*2-2]);
        vector<int>pos(n*2+1);
        for(int j=0;j++<n;)
            pos[v[j].fi]=pos[v[j].se]=j;
        fill(chk,chk+n+1,0);
        if(s!=1)
        {
            put(pos[1]);
            for(int j=n*2;j>s;put(pos[j--]))
                pos[j]=par(pos[j]);
            pos[s]=par(pos[s]);
        }
        if(pos[s]<mx)
            mx=pos[s],mi=i;
        ps=1;
        while(chk[ps])
            ps++;
    }
    for(int i=n;i>n-30;i--)
    {
        vector<pi>v(n+1);
        for(int j=1;j<i;j++)
            v[j]=pi(p[j*2-2],p[j*2-1]);
        v[i]=pi(s,p[i*2-2]);
        for(int j=i;j++<n;)
            v[j]=pi(p[j*2-3],p[j*2-2]);
        vector<int>pos(n*2+1);
        for(int j=0;j++<n;)
            pos[v[j].fi]=pos[v[j].se]=j;
        fill(chk,chk+n+1,0);
        if(s!=1)
        {
            put(pos[1]);
            for(int j=n*2;j>s;put(pos[j--]))
                pos[j]=par(pos[j]);
            pos[s]=par(pos[s]);
        }
        if(pos[s]<mx)
            mx=pos[s],mi=i;
    }
    for(int i=min(ps+5000000/n,n);i>max(ps-10000000/n,0);i--)
    {
        vector<pi>v(n+1);
        for(int j=1;j<i;j++)
            v[j]=pi(p[j*2-2],p[j*2-1]);
        v[i]=pi(s,p[i*2-2]);
        for(int j=i;j++<n;)
            v[j]=pi(p[j*2-3],p[j*2-2]);
        vector<int>pos(n*2+1);
        for(int j=0;j++<n;)
            pos[v[j].fi]=pos[v[j].se]=j;
        fill(chk,chk+n+1,0);
        if(s!=1)
        {
            put(pos[1]);
            for(int j=n*2;j>s;put(pos[j--]))
                pos[j]=par(pos[j]);
            pos[s]=par(pos[s]);
        }
        if(pos[s]<mx||i>mi)
            mx=pos[s],mi=i;
    }
    cout<<mi<<endl;
    return 0;
}

Subtask #1
5.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Incorrect 1776 ms 428 KB Output isn't correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 29 ms 392 KB Output is correct

Subtask #2
64.0 / 94.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 36 ms 384 KB Output is correct
3 Incorrect 1957 ms 416 KB Output isn't correct
4 Incorrect 3 ms 512 KB Output isn't correct
5 Correct 32 ms 1664 KB Output is correct
6 Correct 33 ms 384 KB Output is correct
7 Incorrect 1419 ms 404 KB Output isn't correct
8 Incorrect 3 ms 512 KB Output isn't correct
9 Correct 4 ms 512 KB Output is correct
10 Incorrect 1675 ms 384 KB Output isn't correct
11 Incorrect 9 ms 512 KB Output isn't correct
12 Incorrect 1458 ms 436 KB Output isn't correct
13 Incorrect 23 ms 1280 KB Output isn't correct
14 Execution timed out 2044 ms 504 KB Time limit exceeded
15 Incorrect 6 ms 640 KB Output isn't correct
16 Correct 34 ms 384 KB Output is correct
17 Correct 1935 ms 384 KB Output is correct
18 Incorrect 1663 ms 424 KB Output isn't correct
19 Correct 1877 ms 448 KB Output is correct
20 Correct 1944 ms 468 KB Output is correct
21 Incorrect 4 ms 512 KB Output isn't correct
22 Correct 6 ms 640 KB Output is correct
23 Incorrect 33 ms 1792 KB Output isn't correct
24 Correct 36 ms 384 KB Output is correct
25 Correct 36 ms 384 KB Output is correct
26 Correct 262 ms 512 KB Output is correct
27 Correct 909 ms 1180 KB Output is correct
28 Incorrect 1172 ms 4040 KB Output isn't correct
29 Correct 81 ms 384 KB Output is correct
30 Correct 256 ms 632 KB Output is correct
31 Correct 836 ms 1120 KB Output is correct
32 Correct 1379 ms 5396 KB Output is correct
33 Correct 36 ms 384 KB Output is correct
34 Correct 31 ms 384 KB Output is correct
35 Correct 116 ms 504 KB Output is correct
36 Correct 210 ms 468 KB Output is correct
37 Incorrect 731 ms 1060 KB Output isn't correct
38 Correct 832 ms 1316 KB Output is correct
39 Correct 29 ms 384 KB Output is correct
40 Correct 36 ms 384 KB Output is correct
41 Correct 168 ms 384 KB Output is correct
42 Correct 150 ms 460 KB Output is correct
43 Correct 745 ms 532 KB Output is correct
44 Correct 662 ms 812 KB Output is correct
45 Correct 752 ms 1132 KB Output is correct
46 Correct 714 ms 1196 KB Output is correct
47 Correct 1364 ms 6140 KB Output is correct