oj.uz

답안 #271725

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
271725 2020-08-18T07:21:06 Z 최은수(#5096) Archery (IOI09_archery) C++17
20 / 100
 2000 ms 6084 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<=200)
    {
        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)
        return cout<<r%n+1<<endl,0;
    int mx=inf,mi=-1;
    for(int i=0;i<min(n,1000);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;
    }
    cout<<mi<<endl;
    return 0;
}

Subtask #1
4.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 15 ms 384 KB Output isn't correct
3 Correct 6 ms 384 KB Output is correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 29 ms 384 KB Output is correct

Subtask #2
16.0 / 94.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 36 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Incorrect 4 ms 512 KB Output isn't correct
5 Incorrect 32 ms 1664 KB Output isn't correct
6 Correct 32 ms 384 KB Output is correct
7 Incorrect 1 ms 384 KB Output isn't correct
8 Incorrect 3 ms 512 KB Output isn't correct
9 Incorrect 4 ms 512 KB Output isn't correct
10 Incorrect 1 ms 384 KB Output isn't correct
11 Incorrect 4 ms 512 KB Output isn't correct
12 Incorrect 1 ms 384 KB Output isn't correct
13 Incorrect 23 ms 1280 KB Output isn't correct
14 Incorrect 1 ms 384 KB Output isn't correct
15 Incorrect 6 ms 640 KB Output isn't correct
16 Correct 34 ms 384 KB Output is correct
17 Incorrect 1 ms 384 KB Output isn't correct
18 Incorrect 1 ms 384 KB Output isn't correct
19 Incorrect 1 ms 384 KB Output isn't correct
20 Incorrect 1 ms 384 KB Output isn't correct
21 Incorrect 4 ms 512 KB Output isn't correct
22 Incorrect 6 ms 640 KB Output isn't correct
23 Incorrect 38 ms 1792 KB Output isn't correct
24 Correct 43 ms 504 KB Output is correct
25 Incorrect 33 ms 384 KB Output isn't correct
26 Incorrect 150 ms 632 KB Output isn't correct
27 Incorrect 1178 ms 1248 KB Output isn't correct
28 Execution timed out 2075 ms 4612 KB Time limit exceeded
29 Incorrect 51 ms 384 KB Output isn't correct
30 Incorrect 123 ms 528 KB Output isn't correct
31 Incorrect 1004 ms 992 KB Output isn't correct
32 Execution timed out 2078 ms 5660 KB Time limit exceeded
33 Correct 35 ms 384 KB Output is correct
34 Correct 40 ms 504 KB Output is correct
35 Incorrect 48 ms 384 KB Output isn't correct
36 Incorrect 69 ms 384 KB Output isn't correct
37 Incorrect 748 ms 1040 KB Output isn't correct
38 Incorrect 1109 ms 1232 KB Output isn't correct
39 Correct 29 ms 384 KB Output is correct
40 Incorrect 28 ms 384 KB Output isn't correct
41 Incorrect 72 ms 384 KB Output isn't correct
42 Incorrect 60 ms 384 KB Output isn't correct
43 Incorrect 226 ms 512 KB Output isn't correct
44 Incorrect 389 ms 752 KB Output isn't correct
45 Incorrect 894 ms 972 KB Output isn't correct
46 Incorrect 972 ms 1184 KB Output isn't correct
47 Execution timed out 2075 ms 6084 KB Time limit exceeded