Submission #51261

#	Time	Username	Problem	Language	Result	Execution time	Memory
51261		Mamnoon_Siam	Jousting tournament (IOI12_tournament)	C++17	49 / 100	1086 ms	6600 KiB

tournament

//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'

typedef pair<int, int> ii;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

inline int myrand(int l, int r) {
	int ret = rand(); ret <<= 15; ret ^= rand();
	if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
	return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
    return os<<"(" <<p.first<<", "<<p.second<<")"; }

template<typename T> using min_pq =
	priority_queue<T, vector<T>, greater<T> >;

//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};

vector<int> K, S, E;
int N, C, R;
vector<ii> intervals;
vector<int> val;

int get_max(int l, int r) {
	int mx = -1;
	for(int i = l; i <= r; i++) {
		mx = max(mx, K[i]);
	} return mx;
}

int GetBestPosition(int _N, int _C, int _R, int *_K, int *_S, int *_E) {
	N = _N, C = _C, R = _R;
	K.assign(N - 1, 0), S.assign(C, 0), E.assign(C, 0);
	for(int i = 0; i < N - 1; i++) K[i] = _K[i];
	for(int i = 0; i < C; i++) S[i] = _S[i], E[i] = _E[i];
	ordered_set os;
	for(int i = 0; i < N; i++) {
		os.insert(ii(i, i));
	}
	for(int i = 0; i < C; i++) {
		vector<ii> dlt;
		auto l_it = os.find_by_order(S[i]);
		auto r_it = os.find_by_order(E[i]);
		ii in = ii(l_it -> first, r_it -> second);
		r_it++;
		for(auto it = l_it; it != r_it; it++) dlt.push_back(*it);
		for(int i = 0; i < dlt.size(); i++) os.erase(dlt[i]);
		os.insert(in);
		intervals.push_back(in);
	} val.resize(intervals.size());
	for(int i = 0; i < intervals.size(); i++) {
		val[i] = get_max(intervals[i].first, intervals[i].second - 1);
	}
	int mx = -1, id = -1;
	for(int i = 0; i < N; i++) {
		int c = 0;
		for(int j = 0; j < intervals.size(); j++) {
			if(intervals[j].first <= i and i <= intervals[j].second and val[j] < R) {
				c++;
			}
		}
		if(c > mx) {
			mx = c;
			id = i;
		}
	}
	return id;
}

Compilation message (stderr)

tournament.cpp: In function 'int myrand(int, int)':
tournament.cpp:22:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
  ^~
tournament.cpp:22:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
                          ^~~
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < dlt.size(); i++) os.erase(dlt[i]);
                  ~~^~~~~~~~~~~~
tournament.cpp:67:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < intervals.size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~
tournament.cpp:73:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < intervals.size(); j++) {
                  ~~^~~~~~~~~~~~~~~~~~

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