Submission #867304

#	Time	Username	Problem	Language	Result	Execution time	Memory
867304		HuyQuang_re_Zero	Archery (IOI09_archery)	C++14	100 / 100	318 ms	20620 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 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 label(int k)
{
    return 1-(k<w)+(k>w);
}
struct pt { int pos,jump; };
pt cal1(int x)
{
    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);
        // 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 };
        }
    }
}
pt cal2(int x)
{
    int m=0,i,cnt[3];
    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+=2) a[(i+1)/2]={ label(b[i]),label(b[i+1]) };
   // for(i=1;i<=n;i++) cout<<a[i].fst<<" "<<a[i].snd<<'\n';
    memset(cnt,0,sizeof(cnt));
    int jump=0;
    cnt[a[1].fst]++; cnt[a[1].snd]++;
    a[1].fst=a[1].snd=0;
    for(int step=0;step<=2;step++)
    {
        jump+=cnt[1];
        for(i=n;i>1;i--)
        {
            cnt[a[i].fst]++; cnt[a[i].snd]++;
            if(cnt[2]>0) { cnt[2]--; a[i].fst=2; a[i].snd=0; }
            else if(cnt[1]>0) { cnt[1]--; a[i].fst=1; a[i].snd=0; }
            else a[i].fst=a[i].snd=0;
        }
    }
    for(i=1;i<=n;i++)
        if(a[i].fst==1 || a[i].snd==1)
        {
            return { i,jump };
        }
 //   for(i=1;i<=n;i++) cout<<a[i].fst<<" "<<a[i].snd<<'\n';
}

pt cal(int x)
{
    if(w<=n+1) return cal1(x);
    return cal2(x);
}
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<<n; return 0; }
   // cal(2); return 0;
    //  for(int pos=1;pos<=2*n;pos++) cout<<(pos+1)/2<<" "<<Final(pos)+1<<'\n';
    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:132:13: warning: unused variable 'jump' [-Wunused-variable]
  132 |         int jump=k.jump,pos=k.pos;
      |             ^~~~
archery.cpp: In function 'pt cal1(int)':
archery.cpp:72:1: warning: control reaches end of non-void function [-Wreturn-type]
   72 | }
      | ^
archery.cpp: In function 'pt cal2(int)':
archery.cpp:102:1: warning: control reaches end of non-void function [-Wreturn-type]
  102 | }
      | ^

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