제출 #1153081

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153081		julia_08	Jousting tournament (IOI12_tournament)	C++20	0 / 100	0 ms	320 KiB

tournament

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

const int MAXN = 5e3 + 10;

int pos[MAXN], a[MAXN], cnt[MAXN], marc[MAXN];

int GetBestPosition(int n, int c, int r, int *k, int *s, int *e){

  for(int i=c; i>=1; i--){
    s[i] = s[i - 1] + 1;
    e[i] = e[i - 1] + 1;
  }

  for(int i=n; i>=1; i--){
    k[i] = k[i - 1];
  }

  for(int i=1; i<=n+1; i++){
    pos[i] = i;
    marc[i] = 0;
  }

  for(int i=1; i<=c; i++){

    int j = 0, cur = 0;

    while(cur < s[i]){
      j ++;
      if(!marc[j]) cur ++;
    }

    s[i] = j;

    j = 0, cur = 0;

    while(cur <= e[i]){
      j ++;
      if(!marc[j]) cur ++;
    }

    e[i] = j - 1;

    for(int j=s[i]+1; j<=e[i]; j++) marc[j] = 1;

  }

  for(int i=1; i<n; i++){
    if(k[i] > r) k[i] = 1;
    if(k[i] < r) k[i] = 0;
  }

  /*for(int i=1; i<=c; i++){
    cout << s[i] << " " << e[i] << "\n";
  }*/

  // brutando a pos inicial:

  pair<int, int> best = {-1, 0};

  for(int i=1; i<=n; i++){

    for(int j=1; j<i; j++) a[j] = k[j];

    a[i] = 0;

    for(int j=i+1; j<=n; j++) a[j] = k[j - 1];

    for(int j=1; j<=n; j++) cnt[j] = cnt[j - 1] + (a[j] == 1);

    int ans = 0;

    for(int j=1; j<=c; j++){
      if(s[i] <= i && i <= e[i]){
        if(cnt[e[i]] - cnt[s[i] - 1] == 0){
          ans ++;
        }
      }
    }

    if(ans > best.first){
      best = {ans, i};

    } else if(ans == best.first){
      if(i < best.second){
        best = {ans, i};
      }
    }

  }

  return best.second;
}

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