oj.uz

Submission #317933

# Submission time Handle Problem Language Result Execution time Memory
317933 2020-10-30T21:49:23 Z ant101 Archery (IOI09_archery) C++14
67 / 100
 2000 ms 8784 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-350000000/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-15000000/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 1 ms 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Incorrect 1832 ms 504 KB Output isn't correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 31 ms 504 KB Output is correct

Subtask #2
62.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 Execution timed out 2028 ms 384 KB Time limit exceeded
4 Incorrect 4 ms 640 KB Output isn't correct
5 Correct 33 ms 3960 KB Output is correct
6 Correct 28 ms 512 KB Output is correct
7 Incorrect 1452 ms 504 KB Output isn't correct
8 Incorrect 3 ms 640 KB Output isn't correct
9 Correct 4 ms 768 KB Output is correct
10 Incorrect 1629 ms 384 KB Output isn't correct
11 Incorrect 5 ms 768 KB Output isn't correct
12 Incorrect 1493 ms 384 KB Output isn't correct
13 Incorrect 23 ms 2936 KB Output isn't correct
14 Execution timed out 2045 ms 512 KB Time limit exceeded
15 Incorrect 6 ms 1024 KB Output isn't correct
16 Correct 34 ms 384 KB Output is correct
17 Correct 1991 ms 424 KB Output is correct
18 Incorrect 1751 ms 504 KB Output isn't correct
19 Correct 1988 ms 504 KB Output is correct
20 Execution timed out 2033 ms 512 KB Time limit exceeded
21 Incorrect 4 ms 896 KB Output isn't correct
22 Correct 6 ms 896 KB Output is correct
23 Incorrect 34 ms 4096 KB Output isn't correct
24 Correct 35 ms 384 KB Output is correct
25 Correct 39 ms 384 KB Output is correct
26 Correct 287 ms 512 KB Output is correct
27 Correct 1286 ms 1336 KB Output is correct
28 Incorrect 1556 ms 6080 KB Output isn't correct
29 Correct 86 ms 384 KB Output is correct
30 Correct 268 ms 572 KB Output is correct
31 Correct 1188 ms 1500 KB Output is correct
32 Correct 1790 ms 8096 KB Output is correct
33 Correct 35 ms 384 KB Output is correct
34 Correct 31 ms 384 KB Output is correct
35 Correct 122 ms 384 KB Output is correct
36 Correct 203 ms 504 KB Output is correct
37 Incorrect 1047 ms 1248 KB Output isn't correct
38 Correct 1077 ms 1652 KB Output is correct
39 Correct 29 ms 384 KB Output is correct
40 Correct 37 ms 512 KB Output is correct
41 Correct 186 ms 384 KB Output is correct
42 Correct 171 ms 384 KB Output is correct
43 Correct 1042 ms 632 KB Output is correct
44 Correct 923 ms 948 KB Output is correct
45 Correct 1060 ms 1272 KB Output is correct
46 Correct 1033 ms 1408 KB Output is correct
47 Correct 1723 ms 8784 KB Output is correct