Submission #59049

#	Time	Username	Problem	Language	Result	Execution time	Memory
59049		Bodo171	Jousting tournament (IOI12_tournament)	C++14	0 / 100	32 ms	4276 KiB

tournament

#include <vector>
#include <iostream>
using namespace std;
const int nmax=100005;
vector<int> v[nmax];
int aib[nmax],mx[nmax],wh[nmax],p[nmax],dp[nmax];
int n,i,j,st,dr,act,nod,maxim,opt;
inline int lbit(int x)
{
    return ((x^(x-1))&x);
}
void update(int poz,int val)
{
    for(int idx=poz;idx<=n;idx+=lbit(idx))
        aib[idx]+=val;
}
int get_kth(int k)
{
    int poz=0,curr=0;
    for(int p=16;p>=0;p--)
        if(poz+(1<<p)<=n&&curr+aib[poz+(1<<p)]<k)
           poz+=(1<<p),curr+=aib[poz];
    poz++;
    return poz;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {

  for(i=0;i<n-1;i++)
  {
      update(i+1,1);
  }
  for(i=0;i<C;i++)
  {
      st=S[i]+1;dr=E[i]+1;
      for(j=dr;j>=st;j--)
      {
          act=get_kth(j);
          mx[i]=max(mx[i],K[act-1]);
          if(p[act]) v[i].push_back(p[act]),mx[i]=max(mx[i],mx[p[act]]);
          if(j==st) p[act]=i;
          else update(act,-1);
      }
      if(mx[i]<=R)
      {
          dp[i]=1,wh[i]=act;
          for(j=0;j<v[i].size();j++)
          {
              nod=v[i][j];
              if(dp[nod]+1>dp[i]||(dp[nod]+1==dp[i]&&wh[nod]<dp[i]))
                dp[i]=dp[nod]+1,wh[i]=wh[nod];
          }
          if((dp[i]>maxim)||(dp[i]==maxim&&wh[i]<opt))
            maxim=dp[i],opt=wh[i];
      }
  }
  return opt;

}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
           for(j=0;j<v[i].size();j++)
                   ~^~~~~~~~~~~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51