제출 #289404

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
289404		user202729	팀들 (IOI15_teams)	C++17	77 / 100	4108 ms	197520 KiB

teams

// moreflags=grader.cpp
//
// 10
#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)*3<=((int)splits.size()-j)*2)
		{
			for(int index=last; index<bounds[k]; ++index)
				if(students[index].second>=k)
					rights.push({students[index].second, 1});
		}else{
			int lastValue=0;
			for(int l=(int)splits.size(); l-->j;){
				int const queryLeft=splits[l];
				int const queryRight=l+1==(int)splits.size() ? tree.number: splits[l+1];
				assert(queryLeft<queryRight);

				int const value=tree.get(roots[bounds[k]], queryLeft)-tree.get(roots[last], queryLeft);
				assert(lastValue==tree.get(roots[bounds[k]], queryRight)-tree.get(roots[last], queryRight));
				int const count=value-lastValue;
				lastValue=value;

				assert(count>=0);
				assert(count==std::count_if(students.begin()+last, students.begin()+bounds[k],
							[&](auto value){return queryLeft<=value.second and value.second<queryRight;}));
				if(count>0) rights.push({queryLeft, count});
			}
		}

		/*
		auto const extract=[&](auto extract, int node, int multiplier, int left, int right, int updateLeft, int updateRight){
			extract(extract, tree.data[node].children[0], multiplier, left, middle);
			extract(extract, tree.data[node].children[1], multiplier, middle, right);
		};
		extract(extract, roots[bounds[k]], 1, 0, tree.number, j, (int)splits.size());
		extract(extract, roots[last], -1, 0, tree.number, j, (int)splits.size());
		*/





		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;

}

컴파일 시 표준 에러 (stderr) 메시지

teams.cpp:35:52: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   35 |  int set(int node, int left, int right, int index, auto getter /* old -> new */){
      |                                                    ^~~~
teams.cpp:54:31: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   54 |  int set(int node, int index, auto getter /* old -> new */){
      |                               ^~~~
teams.cpp: In constructor 'Persistent::Persistent(int)':
teams.cpp:22:26: warning: declaration of 'number' shadows a member of 'Persistent' [-Wshadow]
   22 |  Persistent(int number=0): number(number){
      |                          ^
teams.cpp:21:6: note: shadowed declaration is here
   21 |  int number;
      |      ^~~~~~
teams.cpp: In constructor 'Persistent::Persistent(int)':
teams.cpp:27:2: warning: declaration of 'number' shadows a member of 'Persistent' [-Wshadow]
   27 |  }
      |  ^
teams.cpp:21:6: note: shadowed declaration is here
   21 |  int number;
      |      ^~~~~~
teams.cpp: In constructor 'Persistent::Persistent(int)':
teams.cpp:27:2: warning: declaration of 'number' shadows a member of 'Persistent' [-Wshadow]
   27 |  }
      |  ^
teams.cpp:21:6: note: shadowed declaration is here
   21 |  int number;
      |      ^~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:117:12: warning: declaration of 'index' shadows a previous local [-Wshadow]
  117 |    for(int index=last; index<bounds[k]; ++index)
      |            ^~~~~
teams.cpp:107:10: note: shadowed declaration is here
  107 |  for(int index=0; index<M; ++index){
      |          ^~~~~
teams.cpp:124:15: warning: unused variable 'queryRight' [-Wunused-variable]
  124 |     int const queryRight=l+1==(int)splits.size() ? tree.number: splits[l+1];
      |               ^~~~~~~~~~

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