oj.uz

Submission #271875

# Submission time Handle Problem Language Result Execution time Memory
271875 2020-08-18T07:51:50 Z 최은수(#5096) Archery (IOI09_archery) C++17
59 / 100
 2000 ms 6120 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-400000000/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+10000000/n,n);i>max(ps-20000000/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 Execution timed out 2090 ms 384 KB Time limit exceeded
5 Correct 1 ms 384 KB Output is correct
6 Correct 33 ms 388 KB Output is correct

Subtask #2
54.0 / 94.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 48 ms 384 KB Output is correct
3 Execution timed out 2069 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 Incorrect 1722 ms 384 KB Output isn't correct
8 Incorrect 3 ms 512 KB Output isn't correct
9 Correct 5 ms 512 KB Output is correct
10 Incorrect 1936 ms 404 KB Output isn't correct
11 Incorrect 4 ms 512 KB Output isn't correct
12 Incorrect 1762 ms 440 KB Output isn't correct
13 Incorrect 27 ms 1280 KB Output isn't correct
14 Execution timed out 2039 ms 416 KB Time limit exceeded
15 Incorrect 6 ms 640 KB Output isn't correct
16 Correct 34 ms 384 KB Output is correct
17 Execution timed out 2070 ms 384 KB Time limit exceeded
18 Execution timed out 2089 ms 384 KB Time limit exceeded
19 Execution timed out 2075 ms 384 KB Time limit exceeded
20 Execution timed out 2092 ms 384 KB Time limit exceeded
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 39 ms 384 KB Output is correct
25 Correct 36 ms 384 KB Output is correct
26 Correct 421 ms 512 KB Output is correct
27 Correct 1800 ms 1276 KB Output is correct
28 Execution timed out 2062 ms 4192 KB Time limit exceeded
29 Correct 82 ms 384 KB Output is correct
30 Correct 386 ms 512 KB Output is correct
31 Correct 1617 ms 1212 KB Output is correct
32 Execution timed out 2041 ms 5548 KB Time limit exceeded
33 Correct 43 ms 384 KB Output is correct
34 Correct 34 ms 384 KB Output is correct
35 Correct 113 ms 508 KB Output is correct
36 Correct 183 ms 384 KB Output is correct
37 Incorrect 1433 ms 1100 KB Output isn't correct
38 Correct 1551 ms 1340 KB Output is correct
39 Correct 35 ms 384 KB Output is correct
40 Correct 27 ms 384 KB Output is correct
41 Correct 167 ms 504 KB Output is correct
42 Correct 143 ms 464 KB Output is correct
43 Correct 1220 ms 532 KB Output is correct
44 Correct 1276 ms 828 KB Output is correct
45 Correct 1482 ms 1048 KB Output is correct
46 Correct 1402 ms 1156 KB Output is correct
47 Execution timed out 2079 ms 6120 KB Time limit exceeded