Submission #867226

#	Time	Username	Problem	Language	Result	Execution time	Memory
867226		HuyQuang_re_Zero	Archery (IOI09_archery)	C++14	50 / 100	2094 ms	19084 KiB

archery

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 1000005
#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,u,target[N],b[N];
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 };
        jump+=(cur2==1);
       // cerr<<cur1<<" "<<cur2<<'\n';
        // 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 Final(int x)
{
    int m=0,i;
    for(i=1;i<x;i++) b[++m]=ori[i];
    b[++m]=w;
    for(i=x;i<=2*n-1;i++) b[++m]=ori[i];
    for(i=1;i<=2*n;i++) target[b[i]]=(i-1)/2;
    for(int step=1;step<=r;step++)
    {
     //   for(i=1;i<=m;i++) cout<<b[i]<<" "<<target[b[i]]<<'\n';
       // cout<<'\n';
        if(b[1]<b[2]) target[b[2]]=n-1; else target[b[1]]=n-1;
        for(i=3;i<=m;i+=2)
            if(b[i]<b[i+1]) target[b[i]]--; else target[b[i+1]]--;
        sort(b+1,b+m+1,[&](int i,int j){ return target[i]<target[j]; });
    }
    return target[w];
}
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];
  //  for(int pos=1;pos<=2*n;pos++) cout<<(pos+1)/2<<" "<<Final(pos)+1<<'\n';
    //cerr<<Final(100);
    if(w==1) { cout<<n; return 0; }
  //  cerr<<cal(8).pos; return 0;
    int l=cal(2*n).jump,r=cal(1).jump;
    res=2*n+1;
    for(i=l;i<=r;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 k=cal(l);
        int jump=k.jump,pos=k.pos;
        l=1,r=2*n;
        while(l<r)
        {
            int mid=(l+r+1)>>1;
            pt x=cal(mid);
            if(x.jump>i) l=mid;
            else if(x.jump<i) r=mid-1;
            else if(x.pos==pos) l=mid;
            else r=mid-1;
        }

        if(res>pos || (res==pos && u<l))
        {
            res=pos;
            u=l;
        }
    }
    cout<<(u+1)/2;
}

Compilation message (stderr)

archery.cpp: In function 'int main()':
archery.cpp:99:13: warning: unused variable 'jump' [-Wunused-variable]
   99 |         int jump=k.jump,pos=k.pos;
      |             ^~~~
archery.cpp: In function 'pt cal(int)':
archery.cpp:56:1: warning: control reaches end of non-void function [-Wreturn-type]
   56 | }
      | ^

• Subtask 1: 4 / 6
• Subtask 2: 46 / 94