oj.uz

Submission #219667

# Submission time Handle Problem Language Result Execution time Memory
219667 2020-04-05T22:40:16 Z FieryPhoenix Jousting tournament (IOI12_tournament) C++11
100 / 100
 109 ms 17272 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 8 ms 5120 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 7 ms 5120 KB Output is correct
9 Correct 7 ms 5120 KB Output is correct
10 Correct 7 ms 5120 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Correct 11 ms 5632 KB Output is correct
3 Correct 9 ms 5248 KB Output is correct
4 Correct 11 ms 5504 KB Output is correct
5 Correct 11 ms 5504 KB Output is correct
6 Correct 15 ms 5376 KB Output is correct
7 Correct 11 ms 5632 KB Output is correct
8 Correct 11 ms 5504 KB Output is correct
9 Correct 9 ms 5248 KB Output is correct
10 Correct 12 ms 5504 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8204 KB Output is correct
2 Correct 109 ms 17272 KB Output is correct
3 Correct 61 ms 8820 KB Output is correct
4 Correct 107 ms 14712 KB Output is correct
5 Correct 105 ms 15352 KB Output is correct
6 Correct 108 ms 11256 KB Output is correct
7 Correct 109 ms 15608 KB Output is correct
8 Correct 109 ms 15608 KB Output is correct
9 Correct 48 ms 8304 KB Output is correct
10 Correct 58 ms 9208 KB Output is correct