oj.uz

Submission #271814

# Submission time Handle Problem Language Result Execution time Memory
271814 2020-08-18T07:37:21 Z 최은수(#5096) Archery (IOI09_archery) C++17
62 / 100
 2000 ms 6176 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<=500)
    {
        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>n-500000000/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 1 ms 384 KB Output is correct
2 Incorrect 23 ms 384 KB Output isn't correct
3 Correct 7 ms 512 KB Output is correct
4 Execution timed out 2082 ms 384 KB Time limit exceeded
5 Correct 1 ms 384 KB Output is correct
6 Correct 40 ms 388 KB Output is correct

Subtask #2
58.0 / 94.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 55 ms 504 KB Output is correct
3 Execution timed out 2082 ms 384 KB Time limit exceeded
4 Incorrect 3 ms 512 KB Output isn't correct
5 Correct 33 ms 1664 KB Output is correct
6 Correct 44 ms 384 KB Output is correct
7 Execution timed out 2082 ms 384 KB Time limit exceeded
8 Incorrect 3 ms 512 KB Output isn't correct
9 Correct 4 ms 512 KB Output is correct
10 Execution timed out 2074 ms 384 KB Time limit exceeded
11 Incorrect 5 ms 512 KB Output isn't correct
12 Execution timed out 2074 ms 384 KB Time limit exceeded
13 Incorrect 23 ms 1280 KB Output isn't correct
14 Execution timed out 2065 ms 384 KB Time limit exceeded
15 Incorrect 6 ms 640 KB Output isn't correct
16 Correct 50 ms 504 KB Output is correct
17 Execution timed out 2077 ms 384 KB Time limit exceeded
18 Execution timed out 2067 ms 384 KB Time limit exceeded
19 Execution timed out 2079 ms 384 KB Time limit exceeded
20 Execution timed out 2077 ms 384 KB Time limit exceeded
21 Incorrect 4 ms 512 KB Output isn't correct
22 Correct 8 ms 640 KB Output is correct
23 Incorrect 33 ms 1792 KB Output isn't correct
24 Correct 46 ms 384 KB Output is correct
25 Correct 36 ms 384 KB Output is correct
26 Correct 253 ms 512 KB Output is correct
27 Correct 892 ms 1492 KB Output is correct
28 Incorrect 1174 ms 4132 KB Output isn't correct
29 Correct 87 ms 384 KB Output is correct
30 Correct 238 ms 632 KB Output is correct
31 Correct 819 ms 1100 KB Output is correct
32 Correct 1389 ms 5380 KB Output is correct
33 Correct 47 ms 508 KB Output is correct
34 Correct 40 ms 384 KB Output is correct
35 Correct 108 ms 504 KB Output is correct
36 Correct 174 ms 384 KB Output is correct
37 Incorrect 688 ms 1068 KB Output isn't correct
38 Correct 725 ms 1492 KB Output is correct
39 Correct 38 ms 384 KB Output is correct
40 Correct 31 ms 384 KB Output is correct
41 Correct 160 ms 504 KB Output is correct
42 Correct 144 ms 384 KB Output is correct
43 Correct 693 ms 632 KB Output is correct
44 Correct 620 ms 1016 KB Output is correct
45 Correct 739 ms 1076 KB Output is correct
46 Correct 697 ms 1112 KB Output is correct
47 Correct 1344 ms 6176 KB Output is correct