oj.uz

Submission #289414

# Submission time Handle Problem Language Result Execution time Memory
289414 2020-09-02T16:09:52 Z user202729 Teams (IOI15_teams) C++17
100 / 100
 1996 ms 203848 KB 
// moreflags=grader.cpp
//
// 10
// that bug would be terrible to debug without a generator...?
#include "teams.h"
#include<vector>
#include<queue>
#include<functional>
#include<algorithm>
#include<numeric>
#if LOCAL
#include<iostream>
#else
#define NDEBUG
#endif
#include<cassert>

struct Persistent{
	struct Node{int value; std::array<int, 2> children;};
	// value is sum of current subtree
	std::vector<Node> data;
	int number;
	Persistent(int number=0): number(number){
		data.resize(number*4);
		for(int node=0; node<(int)data.size()/2; ++node)
			data[node].children={node*2+1, node*2+2};
		// initially root is 0 and all values are 0
	}

	int makeNode(Node node){
		int const result=(int)data.size();
		data.push_back(node);
		return result;
	}

	int set(int node, int left, int right, int index, auto getter /* old -> new */){
		if(left+1==right){
			//if(data[node].value==value) return node;
			return makeNode(Node{getter(data[node].value), {}});
		}
		int const middle=(left+right)>>1;
		auto copy=data[node];
		if(index>=middle){
			copy.value-=data[copy.children[1]].value;
			copy.children[1]=set(copy.children[1], middle, right, index, getter);
			copy.value+=data[copy.children[1]].value;
		}else{
			copy.value-=data[copy.children[0]].value;
			copy.children[0]=set(copy.children[0], left, middle, index, getter);
			copy.value+=data[copy.children[0]].value;
		}
		return makeNode(copy);
	}

	int set(int node, int index, auto getter /* old -> new */){
		return set(node, 0, number, index, getter);
	}

	int getInternal(int node, int left, int right, int queryLeft, int queryRight)const{
		if(queryLeft>=right or queryRight<=left) return 0;
		if(queryLeft<=left and right<=queryRight) return data[node].value;
		int const middle=(left+right)>>1;
		return getInternal(data[node].children[0], left, middle, queryLeft, queryRight)+
			getInternal(data[node].children[1], middle, right, queryLeft, queryRight);
	}
	int get(int node, int queryLeft, int queryRight)const{
		return getInternal(node, 0, number, queryLeft, queryRight);
	}

	int getInternal(int node, int left, int right, int queryLeft)const{
		if(queryLeft>=right) return 0;
		if(queryLeft<=left) return data[node].value;
		int const middle=(left+right)>>1;
		return getInternal(data[node].children[0], left, middle, queryLeft)+
			getInternal(data[node].children[1], middle, right, queryLeft);
	}
	int get(int node, int queryLeft)const{ // equal to queryRight==number
		return getInternal(node, 0, number, queryLeft);
	}
};

std::vector<std::pair<int, int>> students;
Persistent tree;
std::vector<int> roots;
std::vector<int> bounds;
// students[bounds[i-1]..bounds[i]].left = i
std::vector<char> possible;

int can(int M, int K[]) {
	if(std::accumulate(K, K+M, (int64_t)0)>(int)students.size()) return 0;
	for(int index=0; index<M; ++index) if(not possible[K[index]]) return 0;

	std::sort(K, K+M);
	struct Item{
		int value;
		mutable int count;

		bool operator<(Item other) const{return value>other.value;}
	};
	std::priority_queue<Item> rights;
	//std::map<int, int> rights;


	std::vector<int> splits(K, K+M);
	splits.erase(std::unique(begin(splits), end(splits)), end(splits));

	int last=0;
	for(int index=0; index<M; ++index){
		auto const k=K[index];
		if(k>(int)students.size()) return 0;
		while(not rights.empty() and rights.top().value<k)
			rights.pop();

		auto j=int(std::lower_bound(begin(splits), end(splits), k)-begin(splits));
		assert(splits[j]==k);

		/*
		if((bounds[k]-last)<=((int)splits.size()-j))
		{
			for(int index=last; index<bounds[k]; ++index)
				if(students[index].second>=k)
					rights.push({students[index].second, 1});
		}else{
		*/

		auto const get=[&](int index){
			return tree.get(roots[bounds[k]], splits[index])-tree.get(roots[last], splits[index]);
		};
		auto const extract=[&](auto extract, int updateLeft, int updateRight, int valueLeft, int valueRight){
			assert(updateLeft<updateRight);
			assert(valueLeft>=valueRight);
			if(valueLeft==valueRight)
				return;
			if(updateLeft+1==updateRight){
				rights.push({splits[updateLeft], valueLeft-valueRight});
				return;
			}
			auto const updateMiddle=(updateLeft+updateRight)>>1;
			int const valueMiddle=get(updateMiddle);
			extract(extract, updateLeft, updateMiddle, valueLeft, valueMiddle);
			extract(extract, updateMiddle, updateRight, valueMiddle, valueRight);
		};
		extract(extract, j, (int)splits.size(), get(j), 0);

		//}






		assert(last<=bounds[k]);
		last=bounds[k];

		int remain=k;
		while(remain){
			if(rights.empty()) return 0;
			if(remain>=rights.top().count){
				remain-=rights.top().count;
				rights.pop();
			}else{
				rights.top().count-=remain;
				break;
			}
		}
	}
	return 1;
}

void init(int N, int A[], int B[]) {
	students.clear(); students.reserve(N);
	for(int i=0; i<N; ++i)
		students.push_back({A[i], B[i]});
	std::sort(begin(students), end(students));

	roots.reserve((int)students.size());
	roots.clear();
	roots.push_back(0);
	tree=Persistent(N+1);
	for(auto [left, right]: students){
		assert(right<=N); assert(0<left);
		roots.push_back(
				tree.set(roots.back(), right, [&](int value){return value+1;})
				);
	}

	if(0)
	assert(([&]{
		for(auto root: roots){
			for(int index=0; index<tree.number; ++index)
				std::cerr<<tree.get(root, index, index+1)<<' ';
			std::cerr<<" -- ";
			for(int index=0; index<tree.number; ++index)
				std::cerr<<tree.get(root, index, tree.number)<<' ';
			std::cerr<<'\n';
		}
		return true;
	}()));

	bounds.clear();
	bounds.reserve(N+1);
	for(int index=0; index<(int)students.size(); ++index)
		while((int)bounds.size()<students[index].first)
			bounds.push_back(index);
	while((int)bounds.size()<N+1) bounds.push_back((int)students.size());

	possible.assign(students.size()+1, true);
	for(int index=1; index<=(int)students.size(); ++index)
		if(not can(1, &index)) possible[index]=false;

}

Compilation message

teams.cpp:36:52: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   36 |  int set(int node, int left, int right, int index, auto getter /* old -> new */){
      |                                                    ^~~~
teams.cpp:55:31: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   55 |  int set(int node, int index, auto getter /* old -> new */){
      |                               ^~~~
teams.cpp: In constructor 'Persistent::Persistent(int)':
teams.cpp:23:26: warning: declaration of 'number' shadows a member of 'Persistent' [-Wshadow]
   23 |  Persistent(int number=0): number(number){
      |                          ^
teams.cpp:22:6: note: shadowed declaration is here
   22 |  int number;
      |      ^~~~~~
teams.cpp: In constructor 'Persistent::Persistent(int)':
teams.cpp:28:2: warning: declaration of 'number' shadows a member of 'Persistent' [-Wshadow]
   28 |  }
      |  ^
teams.cpp:22:6: note: shadowed declaration is here
   22 |  int number;
      |      ^~~~~~
teams.cpp: In constructor 'Persistent::Persistent(int)':
teams.cpp:28:2: warning: declaration of 'number' shadows a member of 'Persistent' [-Wshadow]
   28 |  }
      |  ^
teams.cpp:22:6: note: shadowed declaration is here
   22 |  int number;
      |      ^~~~~~
teams.cpp: In lambda function:
teams.cpp:126:31: warning: declaration of 'index' shadows a previous local [-Wshadow]
  126 |   auto const get=[&](int index){
      |                               ^
teams.cpp:108:10: note: shadowed declaration is here
  108 |  for(int index=0; index<M; ++index){
      |          ^~~~~
teams.cpp: In lambda function:
teams.cpp:129:102: warning: declaration of 'extract' shadows a previous local [-Wshadow]
  129 |   auto const extract=[&](auto extract, int updateLeft, int updateRight, int valueLeft, int valueRight){
      |                                                                                                      ^
teams.cpp:129:14: note: shadowed declaration is here
  129 |   auto const extract=[&](auto extract, int updateLeft, int updateRight, int valueLeft, int valueRight){
      |              ^~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 256 KB Output is correct
20 Correct 1 ms 256 KB Output is correct
21 Correct 0 ms 256 KB Output is correct
22 Correct 0 ms 256 KB Output is correct
23 Correct 1 ms 256 KB Output is correct
24 Correct 0 ms 256 KB Output is correct
25 Correct 0 ms 256 KB Output is correct
26 Correct 0 ms 256 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 39712 KB Output is correct
2 Correct 143 ms 39664 KB Output is correct
3 Correct 142 ms 39664 KB Output is correct
4 Correct 145 ms 39796 KB Output is correct
5 Correct 99 ms 39668 KB Output is correct
6 Correct 99 ms 39816 KB Output is correct
7 Correct 100 ms 39668 KB Output is correct
8 Correct 104 ms 39920 KB Output is correct
9 Correct 109 ms 39668 KB Output is correct
10 Correct 110 ms 39668 KB Output is correct
11 Correct 94 ms 39664 KB Output is correct
12 Correct 117 ms 39672 KB Output is correct
13 Correct 116 ms 39664 KB Output is correct
14 Correct 127 ms 39668 KB Output is correct
15 Correct 151 ms 39664 KB Output is correct
16 Correct 141 ms 39664 KB Output is correct
17 Correct 110 ms 39664 KB Output is correct
18 Correct 104 ms 39664 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 39668 KB Output is correct
2 Correct 159 ms 39664 KB Output is correct
3 Correct 226 ms 39664 KB Output is correct
4 Correct 166 ms 39664 KB Output is correct
5 Correct 300 ms 39792 KB Output is correct
6 Correct 206 ms 39664 KB Output is correct
7 Correct 111 ms 39844 KB Output is correct
8 Correct 185 ms 39736 KB Output is correct
9 Correct 107 ms 39664 KB Output is correct
10 Correct 123 ms 39680 KB Output is correct
11 Correct 129 ms 39664 KB Output is correct
12 Correct 285 ms 39684 KB Output is correct
13 Correct 502 ms 39684 KB Output is correct
14 Correct 284 ms 39664 KB Output is correct
15 Correct 199 ms 39664 KB Output is correct
16 Correct 192 ms 39668 KB Output is correct
17 Correct 182 ms 39664 KB Output is correct
18 Correct 164 ms 39668 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 914 ms 197208 KB Output is correct
2 Correct 904 ms 197248 KB Output is correct
3 Correct 1142 ms 197208 KB Output is correct
4 Correct 919 ms 197452 KB Output is correct
5 Correct 1075 ms 197192 KB Output is correct
6 Correct 839 ms 200388 KB Output is correct
7 Correct 555 ms 201028 KB Output is correct
8 Correct 804 ms 201284 KB Output is correct
9 Correct 567 ms 201924 KB Output is correct
10 Correct 569 ms 200008 KB Output is correct
11 Correct 685 ms 200364 KB Output is correct
12 Correct 1073 ms 201052 KB Output is correct
13 Correct 1996 ms 202612 KB Output is correct
14 Correct 1284 ms 203848 KB Output is correct
15 Correct 970 ms 203716 KB Output is correct
16 Correct 966 ms 203848 KB Output is correct
17 Correct 722 ms 203208 KB Output is correct
18 Correct 764 ms 203276 KB Output is correct