답안 #867211

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
867211 2023-10-27T23:39:50 Z HuyQuang_re_Zero Archery (IOI09_archery) C++14
0 / 100
2000 ms 22612 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:49:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   49 |         if(i>=2*n && (cur1==1) || (cur2==1))
      |            ~~~~~~~^~~~~~~~~~~~
archery.cpp:57:1: warning: control reaches end of non-void function [-Wreturn-type]
   57 | }
      | ^
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Runtime error 3 ms 4700 KB Execution killed with signal 11
4 Runtime error 5 ms 9308 KB Execution killed with signal 11
5 Execution timed out 2087 ms 2396 KB Time limit exceeded
6 Execution timed out 2048 ms 2396 KB Time limit exceeded
# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 4700 KB Execution killed with signal 11
2 Runtime error 3 ms 4700 KB Execution killed with signal 11
3 Runtime error 3 ms 4956 KB Execution killed with signal 11
4 Runtime error 7 ms 9224 KB Execution killed with signal 11
5 Runtime error 33 ms 22492 KB Execution killed with signal 11
6 Runtime error 3 ms 4700 KB Execution killed with signal 11
7 Runtime error 3 ms 4700 KB Execution killed with signal 11
8 Runtime error 6 ms 9348 KB Execution killed with signal 11
9 Runtime error 7 ms 9304 KB Execution killed with signal 11
10 Runtime error 3 ms 4952 KB Execution killed with signal 11
11 Runtime error 7 ms 9308 KB Execution killed with signal 11
12 Runtime error 5 ms 9308 KB Execution killed with signal 11
13 Runtime error 27 ms 21748 KB Execution killed with signal 11
14 Runtime error 5 ms 9308 KB Execution killed with signal 11
15 Runtime error 10 ms 13660 KB Execution killed with signal 11
16 Runtime error 2 ms 4816 KB Execution killed with signal 11
17 Runtime error 3 ms 4972 KB Execution killed with signal 11
18 Runtime error 3 ms 4956 KB Execution killed with signal 11
19 Runtime error 5 ms 9308 KB Execution killed with signal 11
20 Runtime error 6 ms 9436 KB Execution killed with signal 11
21 Runtime error 7 ms 9308 KB Execution killed with signal 11
22 Runtime error 11 ms 13912 KB Execution killed with signal 11
23 Runtime error 32 ms 22612 KB Execution killed with signal 11
24 Execution timed out 2028 ms 2648 KB Time limit exceeded
25 Execution timed out 2012 ms 2392 KB Time limit exceeded
26 Execution timed out 2069 ms 2396 KB Time limit exceeded
27 Execution timed out 2045 ms 2648 KB Time limit exceeded
28 Execution timed out 2025 ms 4440 KB Time limit exceeded
29 Execution timed out 2036 ms 2392 KB Time limit exceeded
30 Execution timed out 2051 ms 2396 KB Time limit exceeded
31 Execution timed out 2037 ms 2648 KB Time limit exceeded
32 Execution timed out 2039 ms 5468 KB Time limit exceeded
33 Execution timed out 2045 ms 2548 KB Time limit exceeded
34 Execution timed out 2001 ms 2392 KB Time limit exceeded
35 Execution timed out 2007 ms 2392 KB Time limit exceeded
36 Execution timed out 2053 ms 2396 KB Time limit exceeded
37 Execution timed out 2047 ms 2652 KB Time limit exceeded
38 Execution timed out 2091 ms 2648 KB Time limit exceeded
39 Execution timed out 2004 ms 2392 KB Time limit exceeded
40 Execution timed out 2069 ms 2396 KB Time limit exceeded
41 Execution timed out 2044 ms 2396 KB Time limit exceeded
42 Execution timed out 2013 ms 2396 KB Time limit exceeded
43 Execution timed out 2060 ms 2396 KB Time limit exceeded
44 Execution timed out 2093 ms 2392 KB Time limit exceeded
45 Execution timed out 2064 ms 2652 KB Time limit exceeded
46 Execution timed out 2066 ms 2652 KB Time limit exceeded
47 Execution timed out 2005 ms 5968 KB Time limit exceeded