oj.uz

Submission #867212

# Submission time Handle Problem Language Result Execution time Memory
867212 2023-10-27T23:43:25 Z HuyQuang_re_Zero Archery (IOI09_archery) C++14
0 / 100
 2000 ms 20308 KB 
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 500005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
using namespace std;
int n,r,w,ori[N],m,i,res,pos;
II a[N];
int label(int k)
{
    return 1-(k<w)+(k>w);
}
struct pt { int pos,jump; };
pt cal(int x)
{
    //Init
    if(w>n+1) while(1) {};
    int i;
    for(i=1;i<x;i++) a[i]={ (i-1)/2,label(ori[i]) };
    a[x]={ (x-1)/2,label(w) };
    for(i=x;i<=2*n-1;i++) a[i+1]={ i/2,label(ori[i]) };
    m=2*n;


    int cur1=a[1].snd,cur2=a[2].snd,cnt[3],j=3,jump=0;
    memset(cnt,0,sizeof(cnt));
    for(i=1;i<=3*n;i++)
    {
        //Find the winner and loser in target 1
        if(cur1>cur2) swap(cur1,cur2);
        a[++m]={ i+n-1,cur2 };
        cnt[cur2]++;
        jump+=(cur2==1);
        // Find next archer go to target 1
        while(j<=m && a[j].fst<=i) cnt[a[j++].snd]++;
        int to_1;
        if(cnt[0]) to_1=0; else if(cnt[1]) to_1=1; else to_1=2;
        cur2=to_1; cnt[to_1]--;


        if(i>=2*n && ((cur1==1) || (cur2==1)))
        {
            int to_r=r-i,to_r_mod=(r-i+n)%n;
            if(to_r_mod==0) to_r_mod=n;
            if(i>=r) return { n-to_r_mod+1,jump };
            return { n-to_r_mod+1,jump+1+(to_r-1)/n };
        }
    }
}
int main()
{
  //  freopen("archery.inp","r",stdin);
    //freopen("archery.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>r>>w;
    for(i=1;i<=2*n-1;i++) cin>>ori[i];
    if(w==1) { cout<<1; return 0; }
  //  cal(1); return 0;
    res=2*n+1;
    for(i=0;i<=3;i++)
    {
        int l=1,r=2*n;
        while(l<r)
        {
            int mid=(l+r)>>1;
            pt x=cal(mid);
            if(x.jump<=i) r=mid; else l=mid+1;
        }
        pt x=cal(l);
        if(x.jump && res>x.pos)
        {
            res=x.pos;
            pos=l;
        }
    }
    cout<<pos;
}

Compilation message

archery.cpp: In function 'pt cal(int)':
archery.cpp:57:1: warning: control reaches end of non-void function [-Wreturn-type]
   57 | }
      | ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Runtime error 2 ms 4732 KB Execution killed with signal 11
4 Runtime error 4 ms 9308 KB Execution killed with signal 11
5 Execution timed out 2087 ms 2396 KB Time limit exceeded
6 Execution timed out 2025 ms 2392 KB Time limit exceeded

Subtask #2
0 / 94.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 4700 KB Execution killed with signal 11
2 Runtime error 2 ms 4700 KB Execution killed with signal 11
3 Runtime error 3 ms 4956 KB Execution killed with signal 11
4 Runtime error 6 ms 9308 KB Execution killed with signal 11
5 Runtime error 34 ms 20196 KB Execution killed with signal 11
6 Runtime error 2 ms 4700 KB Execution killed with signal 11
7 Runtime error 3 ms 4876 KB Execution killed with signal 11
8 Runtime error 6 ms 9308 KB Execution killed with signal 11
9 Runtime error 7 ms 9180 KB Execution killed with signal 11
10 Runtime error 3 ms 4956 KB Execution killed with signal 11
11 Runtime error 7 ms 9052 KB Execution killed with signal 11
12 Runtime error 5 ms 9308 KB Execution killed with signal 11
13 Runtime error 26 ms 20024 KB Execution killed with signal 11
14 Runtime error 5 ms 9308 KB Execution killed with signal 11
15 Runtime error 13 ms 13404 KB Execution killed with signal 11
16 Runtime error 2 ms 4700 KB Execution killed with signal 11
17 Runtime error 3 ms 4952 KB Execution killed with signal 11
18 Runtime error 3 ms 4940 KB Execution killed with signal 11
19 Runtime error 5 ms 9308 KB Execution killed with signal 11
20 Runtime error 5 ms 9308 KB Execution killed with signal 11
21 Runtime error 7 ms 9308 KB Execution killed with signal 11
22 Runtime error 10 ms 13432 KB Execution killed with signal 11
23 Runtime error 31 ms 20308 KB Execution killed with signal 11
24 Execution timed out 2069 ms 2396 KB Time limit exceeded
25 Execution timed out 2050 ms 2396 KB Time limit exceeded
26 Execution timed out 2029 ms 2392 KB Time limit exceeded
27 Execution timed out 2028 ms 2396 KB Time limit exceeded
28 Execution timed out 2027 ms 2768 KB Time limit exceeded
29 Execution timed out 2024 ms 2392 KB Time limit exceeded
30 Execution timed out 2056 ms 2396 KB Time limit exceeded
31 Execution timed out 2041 ms 2392 KB Time limit exceeded
32 Execution timed out 2056 ms 3164 KB Time limit exceeded
33 Execution timed out 2008 ms 2392 KB Time limit exceeded
34 Execution timed out 2027 ms 2392 KB Time limit exceeded
35 Execution timed out 2093 ms 2392 KB Time limit exceeded
36 Execution timed out 2017 ms 2392 KB Time limit exceeded
37 Execution timed out 2048 ms 2396 KB Time limit exceeded
38 Execution timed out 2050 ms 2392 KB Time limit exceeded
39 Execution timed out 2025 ms 2392 KB Time limit exceeded
40 Execution timed out 2012 ms 2392 KB Time limit exceeded
41 Execution timed out 2039 ms 2396 KB Time limit exceeded
42 Execution timed out 2077 ms 2396 KB Time limit exceeded
43 Execution timed out 2065 ms 2396 KB Time limit exceeded
44 Execution timed out 2059 ms 2396 KB Time limit exceeded
45 Execution timed out 2064 ms 2396 KB Time limit exceeded
46 Execution timed out 2037 ms 2396 KB Time limit exceeded
47 Execution timed out 2058 ms 3420 KB Time limit exceeded