oj.uz

Submission #879755

# Submission time Handle Problem Language Result Execution time Memory
879755 2023-11-28T04:13:15 Z NeroZein Jousting tournament (IOI12_tournament) C++17
17 / 100
 1000 ms 860 KB 
#include "bits/stdc++.h"
using namespace std; 

const int M = 5003;

int tree[M];

void upd(int i, int v) {
  i++; 
  while (i < M) {
    tree[i] += v;
    i += i & -i;
  }
}

int get(int v) {
  int pos = 0, sum = 0; 
  for (int i = 12; i >= 0; --i) {
    if (pos + (1 << i) < M && sum + tree[pos + (1 << i)] < v) {
      pos += 1 << i;
      sum += tree[pos];
    }
  }
  return pos;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  int ret = 0, best = 0; 
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      upd(j, 1); 
    }
    int tmp = 0; 
    for (int j = 0; j < C; ++j) {
      int ql = S[j], qr = E[j];
      vector<int> ppl; 
      for (int k = 0; k < qr - ql + 1; ++k) {
        int f = get(ql + 1 + k); 
        ppl.push_back(f); 
      }
      int mx = 0; 
      for (int k : ppl) {
        mx = max(mx, (k == i ? R : (k < i ? K[k] : K[k - 1])));
      }
      for (int k : ppl) {
        int val = (k == i ? R : (k < i ? K[k] : K[k - 1])); 
        if (val != mx) {
          upd(k, -1); 
        } else if (k == i) {
          tmp++;
        }
      }
    }
    int x = get(1);
    upd(x, -1); 
    if (tmp > best) {
      best = tmp;
      ret = i; 
    }
  }
  return ret;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 32 ms 344 KB Output is correct
4 Correct 34 ms 344 KB Output is correct
5 Correct 14 ms 348 KB Output is correct
6 Correct 41 ms 348 KB Output is correct
7 Correct 34 ms 344 KB Output is correct
8 Correct 34 ms 348 KB Output is correct
9 Correct 13 ms 456 KB Output is correct
10 Correct 18 ms 452 KB Output is correct

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 428 KB Output is correct
2 Execution timed out 1057 ms 604 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1060 ms 860 KB Time limit exceeded
2 Halted 0 ms 0 KB -