oj.uz

Submission #271828

# Submission time Handle Problem Language Result Execution time Memory
271828 2020-08-18T07:39:33 Z 최은수(#5096) Archery (IOI09_archery) C++17
68 / 100
 1412 ms 6240 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;
    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>1&&s<n+2)
    {
        if(n>10000)
            return cout<<n<<endl,0;
        int mx=inf,mi=-1;
        for(int i=n;i>max(0,n-300000000/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
4.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 26 ms 384 KB Output isn't correct
3 Correct 6 ms 384 KB Output is correct
4 Incorrect 1168 ms 424 KB Output isn't correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 45 ms 384 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 47 ms 384 KB Output is correct
3 Incorrect 1316 ms 504 KB Output isn't correct
4 Incorrect 4 ms 640 KB Output isn't correct
5 Correct 39 ms 1792 KB Output is correct
6 Correct 42 ms 384 KB Output is correct
7 Incorrect 1008 ms 408 KB Output isn't correct
8 Incorrect 4 ms 512 KB Output isn't correct
9 Correct 5 ms 640 KB Output is correct
10 Incorrect 1094 ms 404 KB Output isn't correct
11 Incorrect 5 ms 640 KB Output isn't correct
12 Incorrect 998 ms 504 KB Output isn't correct
13 Incorrect 27 ms 1408 KB Output isn't correct
14 Incorrect 1412 ms 476 KB Output isn't correct
15 Incorrect 7 ms 640 KB Output isn't correct
16 Correct 49 ms 384 KB Output is correct
17 Correct 1288 ms 412 KB Output is correct
18 Incorrect 1133 ms 428 KB Output isn't correct
19 Correct 1334 ms 456 KB Output is correct
20 Correct 1408 ms 476 KB Output is correct
21 Incorrect 5 ms 672 KB Output isn't correct
22 Correct 8 ms 740 KB Output is correct
23 Incorrect 35 ms 1792 KB Output isn't correct
24 Correct 66 ms 384 KB Output is correct
25 Correct 39 ms 420 KB Output is correct
26 Correct 253 ms 536 KB Output is correct
27 Correct 892 ms 1096 KB Output is correct
28 Incorrect 1246 ms 4560 KB Output isn't correct
29 Correct 76 ms 384 KB Output is correct
30 Correct 242 ms 512 KB Output is correct
31 Correct 799 ms 1224 KB Output is correct
32 Correct 1355 ms 5476 KB Output is correct
33 Correct 60 ms 384 KB Output is correct
34 Correct 40 ms 384 KB Output is correct
35 Correct 105 ms 384 KB Output is correct
36 Correct 176 ms 384 KB Output is correct
37 Incorrect 686 ms 1120 KB Output isn't correct
38 Correct 731 ms 1296 KB Output is correct
39 Correct 38 ms 384 KB Output is correct
40 Correct 31 ms 504 KB Output is correct
41 Correct 160 ms 384 KB Output is correct
42 Correct 140 ms 464 KB Output is correct
43 Correct 696 ms 632 KB Output is correct
44 Correct 642 ms 772 KB Output is correct
45 Correct 741 ms 1140 KB Output is correct
46 Correct 704 ms 1412 KB Output is correct
47 Correct 1358 ms 6240 KB Output is correct