oj.uz

답안 #271711

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
271711 2020-08-18T07:19:00 Z 최은수(#5096) Archery (IOI09_archery) C++17
20 / 100
 2000 ms 6088 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<max(n,300);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 1 ms 384 KB Output is correct
2 Incorrect 20 ms 384 KB Output isn't correct
3 Correct 5 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 28 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 57 ms 388 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 35 ms 1664 KB Output isn't correct
6 Correct 35 ms 384 KB Output is correct
7 Incorrect 1 ms 384 KB Output isn't correct
8 Incorrect 4 ms 512 KB Output isn't correct
9 Incorrect 4 ms 512 KB Output isn't correct
10 Incorrect 2 ms 384 KB Output isn't correct
11 Incorrect 6 ms 512 KB Output isn't correct
12 Incorrect 2 ms 304 KB Output isn't correct
13 Incorrect 25 ms 1280 KB Output isn't correct
14 Incorrect 1 ms 384 KB Output isn't correct
15 Incorrect 9 ms 640 KB Output isn't correct
16 Correct 54 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 4 ms 512 KB Output isn't correct
22 Incorrect 6 ms 640 KB Output isn't correct
23 Incorrect 37 ms 1812 KB Output isn't correct
24 Correct 48 ms 384 KB Output is correct
25 Incorrect 30 ms 384 KB Output isn't correct
26 Incorrect 730 ms 536 KB Output isn't correct
27 Execution timed out 2082 ms 1060 KB Time limit exceeded
28 Execution timed out 2092 ms 4072 KB Time limit exceeded
29 Incorrect 72 ms 384 KB Output isn't correct
30 Incorrect 605 ms 512 KB Output isn't correct
31 Execution timed out 2079 ms 1092 KB Time limit exceeded
32 Execution timed out 2078 ms 5548 KB Time limit exceeded
33 Correct 36 ms 384 KB Output is correct
34 Correct 38 ms 384 KB Output is correct
35 Incorrect 104 ms 504 KB Output isn't correct
36 Incorrect 161 ms 472 KB Output isn't correct
37 Execution timed out 2097 ms 900 KB Time limit exceeded
38 Execution timed out 2096 ms 1124 KB Time limit exceeded
39 Correct 31 ms 392 KB Output is correct
40 Incorrect 29 ms 504 KB Output isn't correct
41 Incorrect 145 ms 504 KB Output isn't correct
42 Incorrect 141 ms 468 KB Output isn't correct
43 Incorrect 1087 ms 532 KB Output isn't correct
44 Execution timed out 2076 ms 788 KB Time limit exceeded
45 Execution timed out 2097 ms 1068 KB Time limit exceeded
46 Execution timed out 2087 ms 1160 KB Time limit exceeded
47 Execution timed out 2065 ms 6088 KB Time limit exceeded