Submission #290572

#	Time	Username	Problem	Language	Result	Execution time	Memory
290572		user202729	Seats (IOI18_seats)	C++17	11 / 100	4097 ms	53880 KiB

seats

// moreflags=grader.cpp
// 8
// inefficient version
#include "seats.h"
#include<vector>
#include<algorithm>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>

struct MyData{
	static int constexpr blockSize=100;
	struct Pos{int row, col;};
	struct Rectangle{Pos minimum, maximum;
		Rectangle& operator+=(Rectangle other){
			minimum.row=std::min(minimum.row, other.minimum.row);
			minimum.col=std::min(minimum.col, other.minimum.col);
			maximum.row=std::max(maximum.row, other.maximum.row);
			maximum.col=std::max(maximum.col, other.maximum.col);
			return *this;
		}
		Rectangle operator+(Rectangle other) const{return other+=*this;}
		int area() const{
			assert(maximum.row>minimum.row);
			assert(maximum.col>minimum.col);
			return (maximum.row-minimum.row)*(maximum.col-minimum.col);
		}

		static Rectangle from(Pos it){return Rectangle{it, {it.row+1, it.col+1}};}
	};

	struct Cover{Rectangle bound; int missing;
		Cover operator+(Cover other) const{
			auto const resultBound=bound+other.bound;
			auto const resultMissing=resultBound.area()-(
					bound.area()-missing+other.bound.area()-other.missing
					);
			assert(resultMissing>=0);
			return {resultBound, resultMissing};
		}
	};
	struct Block{
		std::vector<Cover> cover;
		std::array<Pos, blockSize> items;
		int number;
		void build(){ // recompute cover. O(number)
			assert(number<=blockSize);
			assert(number!=0);
			cover.clear();
			cover.push_back({Rectangle::from(items[0]), 0});
			for(int index=1; index<number; ++index){
				auto& [prevBound, prevMissing]=cover.back();
				auto const next=Rectangle::from(items[index])+prevBound;
				auto const diff=next.area()-prevBound.area();
				assert(diff>=0);
				if(diff==0){
					assert(prevMissing>0);
					--prevMissing;
				}else{
					cover.push_back({next, prevMissing+diff-1});
				}
			}
		}
		void setWithoutBuild(int index, Pos pos){
			assert(index<number);
			items[index]=pos;
		}
		std::pair<int, Cover> get(Cover previous)const{
			// inefficient
			int result=0;
			for(auto it: cover)
				if((previous+it).missing==0)
					++result;
			return {result, previous+cover.back()};
		}
	};

	int number;
	std::vector<Block> data;
	MyData(){}
	MyData(int const number, std::vector<int> const& R, std::vector<int> const& C):
		number(number), data((number-1)/blockSize+1)
	{
		assert(number!=0);
		for(auto& it: data) it.number=blockSize;
		data.back().number-=(int)data.size()*blockSize-number;
		assert((int)R.size()==number); assert((int)C.size()==number);

		for(int block=0; block<(int)data.size(); ++block)
			for(int index=0; index<data[block].number; ++index)
				data[block].items[index]={R[block*blockSize+index], C[block*blockSize+index]};

		for(auto& it: data) it.build();
	}

	int getResult(){
		Cover current{Rectangle::from(data[0].items[0]), 1};
		int result{};
		for(auto const& it: data){
			auto [count, next]=it.get(current);
			result+=count; current=next;
		}
		assert(current.missing==0); assert(result>0);
		return result;
	}

	Pos get(int index) const{
		assert(0<=index); assert(index<number);
		return data[index/blockSize].items[index%blockSize];
	}

	int swap(int first, int sec){
		auto const x=get(first), y=get(sec);
		data[first/blockSize].setWithoutBuild(first%blockSize, y);
		data[sec/blockSize].setWithoutBuild(sec%blockSize, x);
		data[first/blockSize].build();
		if(first/blockSize!=sec/blockSize)
			data[sec/blockSize].build();

		return getResult();
	}

} myData;

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

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

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