Submission #299513

#	Time	Username	Problem	Language	Result	Execution time	Memory
299513		user202729	Seats (IOI18_seats)	C++17	100 / 100	836 ms	107384 KiB

seats

// moreflags=grader.cpp
// ...
// segment tree delazification is a good idea.
// this is just a little faster.
#include "seats.h"
#include<vector>
#include<climits>
#include<algorithm>
#if LOCAL
#include<iostream>
#else
#define NDEBUG
#endif
#include<cassert>

struct Tree{
	struct T{
		int pminimum, count, sum;
		void operator+=(T other) {
			if(other.count==0) return;

			other.pminimum+=sum;
			sum+=other.sum;
			if(pminimum<other.pminimum){
			}else if(pminimum==other.pminimum){
				count+=other.count;
			}else{
				count=other.count; pminimum=other.pminimum;
			}
		}
		friend T operator+(T first, T sec){first+=sec; return first;}
	};
	std::vector<T> data;
	Tree(){}
	Tree(int number): data(4<<(31^__builtin_clz(number)), {INT_MAX, 0, INT_MAX}){ // this tree is order-sensitive.
	}
	void build(){
		for(int node=int(data.size()/2); --node;)
			data[node]=data[node*2]+data[node*2+1];
	}

	void addSuffix(int left, int value){
		left+=int(data.size()/2);
		assert(data[left].count==1);
		assert(data[left].pminimum==data[left].sum);
		data[left].pminimum=data[left].sum+=value;

		for(left>>=1; left; left>>=1)
			data[left]=data[left*2]+data[left*2+1];
	}

	int get()const{
		// operator+ is commutative
		auto const d=data[1];
		assert(d.pminimum>=4);
		return d.pminimum==4 ? d.count: 0;
	}
};

struct MyData{
	MyData(){}

	//int width;
	std::vector<std::vector<int>> value; // pos -> time (in 0..H*W), with padded (H*W) values
	struct Pos{ int row, col; };
	std::vector<Pos> pos; // time -> pos
	Tree tree;

	template<int factor> void addTree_(Pos minimum, auto handler){
		auto const [r, c]=minimum;
		std::array<int, 4> times{{
			value[r][c],
			value[r+1][c],
			value[r][c+1],
			value[r+1][c+1],
		}};
		std::sort(begin(times), end(times));

		auto const TOP=int(pos.size());
		assert(times[0]<TOP);     handler(times[0], factor);
		if(times[1]==TOP) return; handler(times[1], -factor);
		if(times[2]==TOP) return; handler(times[2], factor*5);
		if(times[3]==TOP) return; handler(times[3], -factor*5);
		// 5 is always greater than 4 => impossible
	}
	template<int factor> void addTreeMemory(Pos minimum){
		addTree_<factor>(minimum, [&](int a, int b){ freeMemory[a]+=b; });
	}
	template<int factor> void addTreeMemoryIndices(Pos minimum){
		addTree_<factor>(minimum, [&](int a, int b){
			if(freeMemory[a]==0) freeIndices.push_back(a);
			freeMemory[a]+=b;
		});
	}

	std::vector<int> freeMemory; // :)
	std::vector<int> freeIndices;

	MyData(int const H, int const W, std::vector<int> const& R_, std::vector<int> const& C_):
		value(H+2, std::vector<int>(W+2, H*W)),
		pos(H*W), tree(H*W), freeMemory(H*W)
	{
		for(int time=0; time<H*W; ++time){
			pos[time]={R_[time], C_[time]};
			value[R_[time]+1][C_[time]+1]=time;
		}

		for(int i=0; i<(int)value.size()-1; ++i)
			for(int j=0; j<(int)value[0].size()-1; ++j){
				addTreeMemory<1>({i, j});
			}
		assert(freeMemory.size()<=tree.data.size()/2);
		for(int a=0; a<(int)freeMemory.size(); ++a){
			tree.data[a+int(tree.data.size()/2)]={freeMemory[a], 1, freeMemory[a]};
			freeMemory[a]=0;
		}
		tree.build();
	}

	int swap(int first, int sec){
		std::swap(pos[first], pos[sec]);

		std::array<std::array<int, 2> /* can be Pos too if it has comparison operators */, 8> minimums{{
			{pos[first].row, pos[first].col},
			{pos[first].row, pos[first].col+1},
			{pos[first].row+1, pos[first].col},
			{pos[first].row+1, pos[first].col+1},
			{pos[sec].row, pos[sec].col},
			{pos[sec].row, pos[sec].col+1},
			{pos[sec].row+1, pos[sec].col},
			{pos[sec].row+1, pos[sec].col+1},
		}};
		std::sort(begin(minimums), end(minimums));
		auto const last=std::unique(begin(minimums), end(minimums));

		std::for_each(minimums.begin(), last, [&](auto it){
			addTreeMemoryIndices<-1>({it[0], it[1]});
		});

		value[pos[first].row+1][pos[first].col+1]=first;
		value[pos[sec].row+1][pos[sec].col+1]=sec;

		std::for_each(minimums.begin(), last, [&](auto it){
			addTreeMemoryIndices<1>({it[0], it[1]});
		});

		for(auto a: freeIndices) if(auto& l=freeMemory[a]){
			tree.addSuffix(a, l);
			l=0;
		}
		freeIndices.clear();

		return tree.get();
	}
} myData;

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	myData=MyData{H, W, std::move(R), std::move(C)};
}

int swap_seats(int a, int b) {
	return myData.swap(a, b);
}

Compilation message (stderr)

seats.cpp:69:50: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   69 |  template<int factor> void addTree_(Pos minimum, auto handler){
      |                                                  ^~~~
seats.cpp: In member function 'void MyData::addTree_(MyData::Pos, auto:1)':
seats.cpp:81:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   81 |   if(times[1]==TOP) return; handler(times[1], -factor);
      |   ^~
seats.cpp:81:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   81 |   if(times[1]==TOP) return; handler(times[1], -factor);
      |                             ^~~~~~~
seats.cpp:82:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   82 |   if(times[2]==TOP) return; handler(times[2], factor*5);
      |   ^~
seats.cpp:82:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   82 |   if(times[2]==TOP) return; handler(times[2], factor*5);
      |                             ^~~~~~~
seats.cpp:83:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   83 |   if(times[3]==TOP) return; handler(times[3], -factor*5);
      |   ^~
seats.cpp:83:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   83 |   if(times[3]==TOP) return; handler(times[3], -factor*5);
      |                             ^~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 20 / 20
• Subtask 4: 6 / 6
• Subtask 5: 33 / 33
• Subtask 6: 30 / 30