Submission #290068

#	Time	Username	Problem	Language	Result	Execution time	Memory
290068		abyyskit	Jousting tournament (IOI12_tournament)	C++14	49 / 100	1092 ms	14072 KiB

tournament

#include<bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for(int i = x; i < y; ++i)
#define pb push_back

int G;
vector<int> base;
int TRACK;
struct node{
	vector<int> e;
	int c = 1;
	int par = -1;
	int ind = -1;
	int l = -1;
	int r = -1;
	int score = 0;
};

vector<node> g;

int Find(int cur, int ind){
//	cout << "cur, ind " << cur << ", " << ind << "\n";
	FOR(i, 0, g[cur].e.size()){
		int nex = g[cur].e[i];
		int wex = g[nex].c;
		if (wex > ind){
			return Find(nex, ind);
		}
		else if (wex <= ind){
			ind -= wex;
		}

	}
	return cur;
}

void Add(int cur, int amount){
//	cout << "here with "<< cur << " size " << amount << "\n";
	FOR(i, 0, amount){
		g[cur].e.pb(G);
		g[G].par = cur;
		G++;
	}
	g[cur].c += amount - 1;
	int par = g[cur].par;
	while(par != -1){
		g[par].c += amount - 1;
		cur = par;
		par = g[cur].par;
	}
}

void initbase(int cur){
	if (g[cur].e.size() == 0){
		base[TRACK] = cur;
		g[cur].ind = TRACK;
		g[cur].l = TRACK;
		g[cur].r = TRACK + 1;
		TRACK++;
		return;
	}
	int L = INT_MAX;
	int R = -1;
	FOR(i, 0, g[cur].e.size()){
		int nex = g[cur].e[i];
		initbase(nex);
		L = min(L, g[nex].l);
		R = max(R, g[nex].r);
	}
	g[cur].l = L;
	g[cur].r = R;
}

vector<int> seg;

void update(int ind, int x){
	ind += seg.size()/2;
	seg[ind] = x;
	ind /= 2;
	while (ind > 0){
		seg[ind] = max(seg[2*ind], seg[2*ind + 1]);
		ind /= 2;
	}
}

int R;

int query(int l, int r){
	//inclusive-exclusive
	l += seg.size()/2;
	r += seg.size()/2;
	int ans = 0;
	while (r > l){
		if (l % 2 == 1){
			ans = max(ans, seg[l]);
			l++;
		}
		if (r % 2 == 1){
			ans = max(ans, seg[r - 1]);
		}
		l /= 2;
		r /= 2;
	}
	return ans;
}

void process(int cur){
	int high = query(g[cur].l, g[cur].r - 1);
	if (high < R){
		g[cur].score = g[g[cur].par].score + 1;
	}
	else{
		g[cur].score = 0;
	}
}

int GetBestPosition(int N, int C, int r, int *K, int *S, int *E) {
	R = r;
	g.resize(2*N);
	base.resize(N);
	TRACK = 0;
	G = 1;
	seg.resize(2*(N-1));
	FOR(i, 0, N - 1){
		update(i,K[i]);
	}
	for(int i = C - 1; i >= 0; --i){
		int ind = Find(0,S[i]);
		Add(ind, E[i] - S[i] + 1);
	}
	initbase(0);
	FOR(i, 0, G){
		process(i);
	}
/*	cout << "Done\n";
	cout << G << "\n";
	FOR(i, 0, G){
		cout << i << ":\n";
		cout << "e: ";
		FOR(j, 0, g[i].e.size()){
			cout << g[i].e[j] << " ";
		}
		cout << "\n";
		cout << "c = " << g[i].c << "\n";
		cout << "par = " << g[i].par << "\n";
		cout << "(l, r) = (" << g[i].l << ", " << g[i].r << ")\n";
		cout << "score = " << g[i].score << "\n";
		cout << "------------------------------\n";
	}
	FOR(i, 0, base.size()){
		cout << base[i] << " ";
	}
	cout << "\n";
	FOR(i, 0, seg.size()){
		cout << i << ": " << seg[i] << "\n";
	}
	*/
	int smax = 0;
	int ind = 0;
	FOR(i, 0, base.size()){
		if (g[base[i]].score > smax){
			smax = g[base[i]].score;
			ind = i;
		}
	}

  return ind;

}

Compilation message (stderr)

tournament.cpp: In function 'int Find(int, int)':
tournament.cpp:3:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
   23 |  FOR(i, 0, g[cur].e.size()){
      |      ~~~~~~~~~~~~~~~~~~~~~             
tournament.cpp:23:2: note: in expansion of macro 'FOR'
   23 |  FOR(i, 0, g[cur].e.size()){
      |  ^~~
tournament.cpp: In function 'void initbase(int)':
tournament.cpp:3:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
   64 |  FOR(i, 0, g[cur].e.size()){
      |      ~~~~~~~~~~~~~~~~~~~~~             
tournament.cpp:64:2: note: in expansion of macro 'FOR'
   64 |  FOR(i, 0, g[cur].e.size()){
      |  ^~~
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:3:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
  160 |  FOR(i, 0, base.size()){
      |      ~~~~~~~~~~~~~~~~~                 
tournament.cpp:160:2: note: in expansion of macro 'FOR'
  160 |  FOR(i, 0, base.size()){
      |  ^~~

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