Submission #698552

#	Time	Username	Problem	Language	Result	Execution time	Memory
698552		arneves	Jousting tournament (IOI12_tournament)	C++17	17 / 100	1098 ms	136840 KiB

tournament

/*
      ______  _____  _______ _     _ _______ __   _  _____  _  _  _
     |_____/ |     | |       |____/  |______ | \  | |     | |  |  |
     |    \_ |_____| |_____  |    \_ ______| |  \_| |_____| |__|__|
    
    
           .      .           .      .           .      .    	
           _\/  \/_           _\/  \/_           _\/  \/_    	
            _\/\/_             _\/\/_             _\/\/_     	
        _\_\_\/\/_/_/_     _\_\_\/\/_/_/_     _\_\_\/\/_/_/_ 	
         / /_/\/\_\ \       / /_/\/\_\ \       / /_/\/\_\ \  	
            _/\/\_             _/\/\_             _/\/\_     	
            /\  /\             /\  /\             /\  /\     	
           '      '           '      '           '      '    	
    
*/

#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cstdint>
#include <cmath>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <vector>

using namespace std;

struct Node {
	int val;
	int weight, size;
	Node *left, *right;
	Node(int c) : val(c), weight(rand()), size(1), left(NULL), right(NULL) {}
};

inline int size(Node *treap) { return treap ? treap->size : 0; }

void split(Node *treap, Node *&left, Node *&right, int val) {
	if (!treap) {
		left = right = NULL;
		return;
	}

	if (size(treap->left) < val) {
		split(treap->right, treap->right, right, val - size(treap->left) - 1);
		left = treap;
	} else {
		split(treap->left, left, treap->left, val);
		right = treap;
	}
	treap->size = 1 + size(treap->left) + size(treap->right);
}

void merge(Node *&treap, Node *left, Node *right) {
	if (left == NULL) {
		treap = right;
		return;
	}
	if (right == NULL) {
		treap = left;
		return;
	}

	if (left->weight < right->weight) {
		merge(left->right, left->right, right);
		treap = left;
	} else {
		merge(right->left, left, right->left);
		treap = right;
	}
	treap->size = 1 + size(treap->left) + size(treap->right);
}

ostream &operator<<(ostream &os, Node *n) {
	if (!n) return os;
	os << n->left;
	os << n->val;
	os << n->right;
	return os;
}

void get(Node *n, vector<int> &v){
	if(!n) return;
	
	v.push_back(n->val);
	get(n->left, v);
	get(n->right, v);
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	
	int ans=-1;
	int best=-1;
	
	for(int pos=0; pos<N; pos++){
		
		Node *root=NULL;
		
		for(int i=0; i<N; i++){
			if(i<pos){
				merge(root, root, new Node(K[i]));
			}else if(i==pos){
				merge(root, root, new Node(R));
			}else{
				merge(root, root, new Node(K[i-1]));
			}
		}
		
		int cur=0;
		
		for(int j=0; j<C; j++){
			
			vector<int> atual;
			Node *a, *b, *c;
			split(root, a, b, S[j]);
			split(b, b, c, E[j]-S[j]+1);
			
			//cout<<a<<' '<<b<<' '<<c<<'\n';
			
			get(b, atual);
			
			int mx=0, ff=0;
			
			for(int u: atual){
				mx=max(mx, u);
				if(R==u) ff=1;
			}
			
			if(mx==R) cur++;
			else if(ff==1) break;
			
			delete(b);
			
			//cout<<a<<' '<<b<<' '<<c<<'\n';
			
			merge(root, a, new Node(mx));
			merge(root, root, c);
			
			//cout<<root<<'\n';
		}
		
		delete(root);
		
		if(cur>best){
			best=cur;
			ans=pos;
		}
	}
	
	return ans;
}

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