Submission #219667

#	Time	Username	Problem	Language	Result	Execution time	Memory
219667		FieryPhoenix	Jousting tournament (IOI12_tournament)	C++11	100 / 100	109 ms	17272 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007

int N,C,R,K[100001],S[100001],E[100001];
int arr[100005];
vector<int>adj[200005];
int ID;
int tree[200005];
int l[200005],r[200005],store[200005];
int dis[200005];
int strong[200005];

void dfs(int node){
  if (node<=N){
    l[node]=node;
    r[node]=node;
    if (strong[r[node]-1]-strong[l[node]-1]==0)
      store[node]=l[node];
    else
      store[node]=INF;
    return;
  }
  l[node]=INF;
  r[node]=-INF;
  store[node]=INF;
  for (int x:adj[node]){
    dfs(x);
    l[node]=min(l[node],l[x]);
    r[node]=max(r[node],r[x]);
    if (store[x]==INF) continue;
    if (dis[x]+1>dis[node]){
      dis[node]=dis[x]+1;
      store[node]=store[x];
    }
    else if (dis[x]+1==dis[node])
      store[node]=min(store[node],store[x]);
  }
}

int query(int pos){
  int ans=0;
  while (pos>=1){
    ans+=tree[pos];
    pos-=(pos&(-pos));
  }
  return ans;
}

void update(int pos, int val){
  while (pos<=N){
    tree[pos]+=val;
    pos+=(pos&(-pos));
  }
}

int getKth(int k){
  int low=0,high=N+1,mid;
  while (low+1<high){
    mid=(low+high)/2;
    //cout<<mid<<' '<<query(mid)<<endl;
    if (query(mid)>=k)
      high=mid;
    else
      low=mid;
  }
  return high;
}

int GetBestPosition(int NN, int CC, int RR, int K[], int S[], int E[]){
  N=NN; C=CC; R=RR;
  for (int i=N-1;i>=1;i--){
    K[i]=K[i-1];
    if (K[i]>R)
      strong[i]++;
  }
  for (int i=1;i<=N;i++)
    strong[i]+=strong[i-1];
  for (int i=1;i<=N;i++){
    arr[i]=i;
    update(i,1);
  }
  ID=N;
  for (int i=0;i<C;i++){
    int len=E[i]-S[i]+1;
    S[i]++; E[i]++;
    ID++;
    int repl;
    for (int j=0;j<len;j++){
      int ind=getKth(S[i]);
      repl=ind;
      adj[ID].push_back(arr[ind]);
      arr[ind]=0;
      update(ind,-1);
    }
    arr[repl]=ID;
    update(repl,1);
  }
  dfs(ID);
  int ans=0,realAns=INF;
  for (int i=ID;i>N;i--){
    if (store[i]!=INF && strong[r[i]-1]-strong[l[i]-1]==0){
      if (dis[i]>ans){
	ans=max(ans,dis[i]);
	realAns=store[i];
      }
      else if (dis[i]==ans)
	realAns=min(realAns,store[i]);
    }
  }
  if (realAns==INF)
    return 0;
  else
    return realAns-1;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:58:8: warning: 'repl' may be used uninitialized in this function [-Wmaybe-uninitialized]
     pos+=(pos&(-pos));
     ~~~^~~~~~~~~~~~~~
tournament.cpp:93:9: note: 'repl' was declared here
     int repl;
         ^~~~

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