Submission #290089

#	Time	Username	Problem	Language	Result	Execution time	Memory
290089		abyyskit	Jousting tournament (IOI12_tournament)	C++14	49 / 100	1090 ms	20088 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;

void update(int ind, int x, vector<int>& fen){
	ind++;
	while (ind < fen.size()){
		fen[ind] += x;
		ind += ind&(-ind);
	}
}

int query(int ind, vector<int> &fen){
	int ans = 0;
	ind++;
	while(ind > 0){
		ans += fen[ind];
		ind -= ind &(-ind);
	}
	return ans;
}


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

vector<node> g;

int Find(int cur, int ind){
//	cout << ind << "\n" << flush;
	if (ind < 0){
		cin >> cur;
	}
//	cout << "cur, ind " << cur << ", " << ind << "\n";
	if (ind == 0 && g[cur].e.size() == 0){
		return cur;
	}
	int l = -1;
	int r = g[cur].w.size() - 2;
	while (r > l + 1){
		int mid = (l + r)/2;
		if (query(mid, g[cur].w) > ind){
			r = mid;
		}
		else{
			l = mid;
		}
	}
//	FOR(i, 0, g[cur].w.size()){
//		cout << query(i, g[cur].w) << " ";
//	}
//	cout << "\n";
//	cout << "l r " << l << " " << r << endl; 
	int tmp = query(l, g[cur].w);
	if (tmp <= ind){
		ind -= tmp;
	}
//	cout << g[cur].e[r] << " " << ind << endl;
	return Find(g[cur].e[r], ind);
	/*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";
	g[cur].w.resize(amount + 1);
	FOR(i, 0, amount){
		g[cur].e.pb(G);
		g[G].par = cur;
		g[G].parind = i;
		update(i, 1, g[cur].w);
		G++;
	}
	g[cur].c += amount - 1;
	int par = g[cur].par;
	while(par != -1){
		update(g[cur].parind, amount - 1, g[par].w);
		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 'void update(int, int, std::vector<int>&)':
tournament.cpp:12:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  while (ind < fen.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)
......
  119 |  FOR(i, 0, g[cur].e.size()){
      |      ~~~~~~~~~~~~~~~~~~~~~             
tournament.cpp:119:2: note: in expansion of macro 'FOR'
  119 |  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)
......
  215 |  FOR(i, 0, base.size()){
      |      ~~~~~~~~~~~~~~~~~                 
tournament.cpp:215:2: note: in expansion of macro 'FOR'
  215 |  FOR(i, 0, base.size()){
      |  ^~~

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