Submission #867211

#	Time	Username	Problem	Language	Result	Execution time	Memory
867211		HuyQuang_re_Zero	Archery (IOI09_archery)	C++14	0 / 100	2093 ms	22612 KiB

archery

#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 (stderr)

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 | }
      | ^

• Subtask 1: 0 / 6
• Subtask 2: 0 / 94