Submission #416155

#	Time	Username	Problem	Language	Result	Execution time	Memory
416155		Theo830	Jousting tournament (IOI12_tournament)	C++17	17 / 100	1089 ms	2208 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll INF = 1e9+7;
ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Deltix Round, Spring 2021 (open for everyone, rated, Div. 1 + Div. 2)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<ll> distr;
ll rnd(ll a, ll b){return distr(rng)%(b-a+1)+a;}
/*
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E);

int main() {
  int tmp;
  char *inbuf, *outbuf;
  inbuf = (char*) malloc(inbuf_len * sizeof(char));
  outbuf = (char*) malloc(outbuf_len * sizeof(char));
  tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
  assert(tmp == 0);
  tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);
  assert(tmp == 0);

  int N, C, R;
  int *K, *S, *E;
  tmp = scanf("%d %d %d", &N, &C, &R);
  assert(tmp == 3);
  K = (int*) malloc((N-1) * sizeof(int));
  S = (int*) malloc(C * sizeof(int));
  E = (int*) malloc(C * sizeof(int));
  int i;
  for (i = 0; i < N-1; i++) {
    tmp = scanf("%d", &K[i]);
    assert(tmp == 1);
  }
  for (i = 0; i < C; i++) {
    tmp = scanf("%d %d", &S[i], &E[i]);
    assert(tmp == 2);
  }

  printf("%d\n", GetBestPosition(N, C, R, K, S, E));

  return 0;

}
*/
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    ll posa = 0;
    ll ans = 0;
    vll arr;
    f(i,0,N){
        ll res = 0;
        arr.clear();
        f(j,0,N-1){
            if(j == i){
                arr.pb(R);
            }
            arr.pb(K[j]);
        }
        if(i == N-1){
            arr.pb(R);
        }
        f(j,0,C){
            ll maxi = 0;
            f(k,S[j],E[j]+1){
                maxi = max(maxi,arr[k]);
            }
            vll neo;
            bool ok = 0;
            f(k,0,S[j]){
                neo.pb(arr[k]);
            }
            neo.pb(maxi);
            ok |= maxi == R;
            f(k,E[j]+1,N){
                neo.pb(arr[k]);
            }
            arr = neo;
            res += ok;
        }
        if(res > posa){
            posa = res;
            ans = i;
        }
    }
    return ans;
}
/*
5 3 3
1
0
2
4
1 3
0 1
0 1
*/

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