oj.uz

답안 #271679

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
271679 2020-08-18T07:11:33 Z 최은수(#5096) Archery (IOI09_archery) C++17
40 / 100
 2000 ms 5960 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=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]);
        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;
        if(mx==1)
            break;
    }
    cout<<mi<<endl;
    return 0;
}

Subtask #1
4.0 / 6.0

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

Subtask #2
36.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 3 ms 512 KB Output isn't correct
5 Incorrect 36 ms 1664 KB Output isn't correct
6 Correct 29 ms 392 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 27 ms 1280 KB Output isn't correct
14 Incorrect 2 ms 384 KB Output isn't correct
15 Incorrect 8 ms 640 KB Output isn't correct
16 Correct 35 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 2 ms 384 KB Output isn't correct
21 Incorrect 5 ms 512 KB Output isn't correct
22 Incorrect 7 ms 640 KB Output isn't correct
23 Incorrect 34 ms 1792 KB Output isn't correct
24 Correct 40 ms 384 KB Output is correct
25 Correct 31 ms 384 KB Output is correct
26 Correct 746 ms 632 KB Output is correct
27 Execution timed out 2076 ms 1228 KB Time limit exceeded
28 Execution timed out 2088 ms 4016 KB Time limit exceeded
29 Correct 74 ms 384 KB Output is correct
30 Correct 603 ms 512 KB Output is correct
31 Execution timed out 2096 ms 976 KB Time limit exceeded
32 Execution timed out 2094 ms 5384 KB Time limit exceeded
33 Correct 35 ms 384 KB Output is correct
34 Correct 32 ms 396 KB Output is correct
35 Correct 108 ms 384 KB Output is correct
36 Correct 169 ms 504 KB Output is correct
37 Execution timed out 2050 ms 1356 KB Time limit exceeded
38 Execution timed out 2078 ms 1388 KB Time limit exceeded
39 Correct 29 ms 384 KB Output is correct
40 Correct 33 ms 384 KB Output is correct
41 Correct 174 ms 384 KB Output is correct
42 Correct 132 ms 384 KB Output is correct
43 Correct 1122 ms 532 KB Output is correct
44 Execution timed out 2096 ms 688 KB Time limit exceeded
45 Execution timed out 2061 ms 1104 KB Time limit exceeded
46 Execution timed out 2078 ms 1368 KB Time limit exceeded
47 Execution timed out 2097 ms 5960 KB Time limit exceeded