oj.uz

Submission #271954

# Submission time Handle Problem Language Result Execution time Memory
271954 2020-08-18T08:06:33 Z 최은수(#5096) Archery (IOI09_archery) C++17
69 / 100
 1965 ms 6216 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>12500)
            return cout<<n<<endl,0;
        int mx=inf,mi=-1;
        for(int i=n;i>max(0,n-320000000/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]=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]=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]=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 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 9 ms 416 KB Output is correct
4 Incorrect 1965 ms 448 KB Output isn't correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 40 ms 384 KB Output is correct

Subtask #2
64.0 / 94.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 36 ms 384 KB Output is correct
3 Incorrect 1954 ms 412 KB Output isn't correct
4 Incorrect 3 ms 512 KB Output isn't correct
5 Correct 33 ms 1784 KB Output is correct
6 Correct 28 ms 384 KB Output is correct
7 Incorrect 1394 ms 408 KB Output isn't correct
8 Incorrect 4 ms 512 KB Output isn't correct
9 Correct 7 ms 512 KB Output is correct
10 Incorrect 1515 ms 400 KB Output isn't correct
11 Incorrect 4 ms 512 KB Output isn't correct
12 Incorrect 1449 ms 436 KB Output isn't correct
13 Incorrect 29 ms 1280 KB Output isn't correct
14 Incorrect 1930 ms 472 KB Output isn't correct
15 Incorrect 7 ms 640 KB Output isn't correct
16 Correct 36 ms 384 KB Output is correct
17 Correct 1936 ms 416 KB Output is correct
18 Incorrect 1725 ms 504 KB Output isn't correct
19 Correct 1826 ms 452 KB Output is correct
20 Correct 1758 ms 472 KB Output is correct
21 Incorrect 5 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 35 ms 384 KB Output is correct
25 Correct 35 ms 384 KB Output is correct
26 Correct 268 ms 512 KB Output is correct
27 Correct 894 ms 1168 KB Output is correct
28 Incorrect 1143 ms 4160 KB Output isn't correct
29 Correct 68 ms 384 KB Output is correct
30 Correct 245 ms 512 KB Output is correct
31 Correct 821 ms 1152 KB Output is correct
32 Correct 1415 ms 5744 KB Output is correct
33 Correct 41 ms 384 KB Output is correct
34 Correct 31 ms 384 KB Output is correct
35 Correct 110 ms 504 KB Output is correct
36 Correct 183 ms 508 KB Output is correct
37 Incorrect 744 ms 944 KB Output isn't correct
38 Correct 751 ms 1260 KB Output is correct
39 Correct 34 ms 384 KB Output is correct
40 Correct 34 ms 384 KB Output is correct
41 Correct 169 ms 384 KB Output is correct
42 Correct 151 ms 464 KB Output is correct
43 Correct 735 ms 532 KB Output is correct
44 Correct 636 ms 692 KB Output is correct
45 Correct 746 ms 1096 KB Output is correct
46 Correct 715 ms 1364 KB Output is correct
47 Correct 1347 ms 6216 KB Output is correct