제출 #66626

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66626		Bodo171	마상시합 토너먼트 (IOI12_tournament)	C++14	0 / 100	51 ms	9024 KiB

tournament

#include <vector>
#include <iostream>
using namespace std;
const int nmax=200005;
vector<int> v[nmax];
int aib[nmax],mx[nmax],wh[nmax],parinte[nmax],dp[nmax],opt[nmax],val[nmax],mxnorm[nmax],mxst[nmax],mxin[nmax],M[nmax];
int K[nmax],S[nmax],E[nmax];
int n,i,j,st,dr,act,nod,maxim,globalopt,mxx;
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) {

  n=N;globalopt=1;
  for(i=0;i<n-1;i++)
  {
      update(i+1,1);
  }
  int tot=n;
  for(i=1;i<=n;i++)
    parinte[i]=R+i,opt[R+i]=i,dp[R+i]=0,val[i]=K[i-1];
  for(i=0;i<C;i++)
  {
      st=S[i]+1;dr=E[i]+1;
      for(j=dr;j>=st;j--)
      {
          if(j<=tot)
          {
            act=get_kth(j);
            if(val[act]>mxnorm[i])
                mxnorm[i]=val[act];
            if(j<dr&&val[act]>mxin[i])
              mxin[i]=val[act];
            if(j<dr&&val[act]>mxst[i])
              mxst[i]=val[act];
            v[i].push_back(parinte[j]);
            update(act,-1);
            tot--;
          }
      }
      if(st>1)
        mxst[i]=max(mxst[i],val[get_kth(st-1)]);
      tot++;
      update(act,1);
      parinte[act]=i;
      val[act]=mxin[i];
      M[v[i].size()]=-1;
      for(j=v[i].size()-1;j>=0;j--)
      {
          M[j]=max(M[j+1],mxnorm[j]);
      }
      int S=-1;
      for(j=0;j<v[i].size();j++)
      {
          nod=v[i][j];
          S=max(S,mxst[nod]);
          if(S<C&&mxin[nod]<C&&M[j+1]<C&&opt[nod])
          {
              if(dp[nod]+1>dp[i]||(dp[nod]+1==dp[i]&&opt[nod]<opt[i]))
                dp[i]=dp[nod]+1,opt[i]=opt[nod];
          }
      }
      if(dp[i]>mxx||(dp[i]==mxx&&opt[i]<globalopt))
        globalopt=opt[i],mxx=dp[i];
  }
  return globalopt-1;

}

컴파일 시 표준 에러 (stderr) 메시지

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:68:16: 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