oj.uz

Submission #271632

# Submission time Handle Problem Language Result Execution time Memory
271632 2020-08-18T07:04:50 Z 최은수(#5096) Archery (IOI09_archery) C++17
34 / 100
 2000 ms 6816 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;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,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;
        vector<bool>chk(n+1,0);
        if(s!=1)
        {
            chk[pos[1]]=1;
            for(int j=n*2;j>=s;chk[pos[j--]]=1)
                while(chk[pos[j]])
                    pos[j]=pos[j]==1?n:pos[j]-1;
        }
        if(pos[s]<mx)
            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 16 ms 424 KB Output isn't correct
3 Correct 7 ms 384 KB Output is correct
4 Incorrect 1 ms 288 KB Output isn't correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 42 ms 392 KB Output is correct

Subtask #2
30.0 / 94.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 51 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Incorrect 5 ms 512 KB Output isn't correct
5 Incorrect 41 ms 3288 KB Output isn't correct
6 Correct 42 ms 384 KB Output is correct
7 Incorrect 1 ms 384 KB Output isn't correct
8 Incorrect 6 ms 640 KB Output isn't correct
9 Incorrect 5 ms 640 KB Output isn't correct
10 Incorrect 1 ms 384 KB Output isn't correct
11 Incorrect 5 ms 640 KB Output isn't correct
12 Incorrect 1 ms 384 KB Output isn't correct
13 Incorrect 25 ms 2792 KB Output isn't correct
14 Incorrect 2 ms 384 KB Output isn't correct
15 Incorrect 8 ms 896 KB Output isn't correct
16 Correct 46 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 5 ms 640 KB Output isn't correct
22 Incorrect 6 ms 768 KB Output isn't correct
23 Incorrect 39 ms 3348 KB Output isn't correct
24 Correct 46 ms 384 KB Output is correct
25 Correct 93 ms 384 KB Output is correct
26 Execution timed out 2055 ms 384 KB Time limit exceeded
27 Execution timed out 2066 ms 1096 KB Time limit exceeded
28 Execution timed out 2072 ms 4924 KB Time limit exceeded
29 Correct 608 ms 424 KB Output is correct
30 Execution timed out 2072 ms 384 KB Time limit exceeded
31 Execution timed out 2077 ms 1188 KB Time limit exceeded
32 Execution timed out 2065 ms 6076 KB Time limit exceeded
33 Correct 45 ms 384 KB Output is correct
34 Correct 39 ms 384 KB Output is correct
35 Correct 205 ms 384 KB Output is correct
36 Correct 426 ms 440 KB Output is correct
37 Execution timed out 2092 ms 1056 KB Time limit exceeded
38 Execution timed out 2081 ms 1328 KB Time limit exceeded
39 Correct 38 ms 384 KB Output is correct
40 Correct 82 ms 384 KB Output is correct
41 Correct 672 ms 504 KB Output is correct
42 Correct 423 ms 504 KB Output is correct
43 Execution timed out 2083 ms 384 KB Time limit exceeded
44 Execution timed out 2089 ms 912 KB Time limit exceeded
45 Execution timed out 2079 ms 1080 KB Time limit exceeded
46 Execution timed out 2095 ms 1192 KB Time limit exceeded
47 Execution timed out 2069 ms 6816 KB Time limit exceeded