Submission #43518

#	Time	Username	Problem	Language	Result	Execution time	Memory
43518		PowerOfNinjaGo	Teams (IOI15_teams)	C++14	77 / 100	4100 ms	335468 KiB

teams

//Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
#include "grader.cpp"
#else
#include "teams.h"
#endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
const int maxn = 5e5+5;
int n;
int a[maxn], b[maxn];
vii vec;
struct node
{
	int v;
	node *left, *right;
	node(){}
	node(int _v, node *a, node *b)
	{
		v = _v;
		left = a; right = b;
	}
	node* insert(int v, int L = 1, int R = n)
	{
		if(L<= v && v<= R)
		{
			if(L == R) return new node(this->v+1, NULL, NULL);
			int M = (L+R)/2;
			return new node(this->v+1, left->insert(v, L, M), right->insert(v, M+1, R));
		}
		return this;
	}
	int ask(int i, int j, int L = 1, int R = n)
	{
		//printf("asked %d %d\n", i,j );
		if(i> R || j< L) return 0;
		if(i<= L && R<= j) return v;
		int M = (L+R)/2;
		int x = left->ask(i, j, L, M), y = right->ask(i, j, M+1, R);
		return x+y;
	}
};
node *zero;
node* root[maxn];
void init(int N, int A[], int B[])
{
	srand(time(NULL));
	n = N;
	for(int i = 0; i< N; i++) a[i] = A[i], b[i] = B[i];
	for(int i = 0; i< N; i++) vec.pb(ii(a[i], b[i]));
	sort(vec.begin(), vec.end());
	zero = new node(0, NULL, NULL);
	zero->left = zero->right = zero;
	root[0] = zero;
	int ptr = 0;
	for(int i = 1; i<= n; i++)
	{
		root[i] = root[i-1];
		while(ptr< n && vec[ptr].X == i) root[i] = root[i]->insert(vec[ptr++].Y);
	}
}
int era[1100];
int can(int M, int K[])
{
	memset(era, 0, sizeof era);
	int sum = 0;
	for(int i = 0; i< M; i++) sum += K[i];
	if(sum> n) return 0;
	sort(K, K+M);
	vi dis; for(int i = 0; i< M; i++) dis.pb(K[i]);
	sort(dis.begin(), dis.end()); dis.resize(unique(dis.begin(), dis.end())-dis.begin());
	int q = dis.size();
	assert(q<= 1200);
	for(int i = 0; i< M; i++)
	{
		int x = K[i];
		int ptr = 0;
		while(dis[ptr]< x) ptr++;
		//printf("%d: %d\n", x, ptr);
		int tmp = ptr;
		while(x && tmp< q)
		{
			//printf("tmp is %d %d\n", tmp, tmp+1< q);
			int here = root[K[i]]->ask(dis[tmp], (tmp+1< q)?dis[tmp+1]-1:n)-era[tmp];
			//printf("from %d to %d is %d\n", dis[tmp], (tmp+1< q)?dis[tmp+1]-1:n, here-era[tmp]);
			if(here<= x)
			{
				x -= here;
				era[tmp] += here;
			}
			else
			{
				era[tmp] += x;
				x = 0;
			}
			tmp++;
		}
		if(x) return 0;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In constructor 'node::node(int, node*, node*)':
teams.cpp:25:2: warning: declaration of 'b' shadows a global declaration [-Wshadow]
  {
  ^
teams.cpp:17:14: note: shadowed declaration is here
 int a[maxn], b[maxn];
              ^
teams.cpp:25:2: warning: declaration of 'a' shadows a global declaration [-Wshadow]
  {
  ^
teams.cpp:17:5: note: shadowed declaration is here
 int a[maxn], b[maxn];
     ^
teams.cpp: In member function 'node* node::insert(int, int, int)':
teams.cpp:30:2: warning: declaration of 'v' shadows a member of 'node' [-Wshadow]
  {
  ^
teams.cpp:21:6: note: shadowed declaration is here
  int v;
      ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:53:18: warning: conversion to 'unsigned int' from 'time_t {aka long int}' may alter its value [-Wconversion]
  srand(time(NULL));
                  ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:78:19: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  int q = dis.size();
                   ^

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 0 / 23