제출 #290578

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
290578		user202729	자리 배치 (IOI18_seats)	C++17	5 / 100	4093 ms	54008 KiB

seats

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

struct MyData{
	static int constexpr blockSize=
#if LOCAL
		2
#else
		1000
#endif
		;
	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);
		}

		bool contains(Rectangle other) const{return area()==(*this+other).area();}

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

	struct Cover{Rectangle bound; int missing;
		int count() const{
			assert(missing<=bound.area());
			return bound.area()-missing;
		};
		Cover operator+(Cover other) const{
			auto const resultBound=bound+other.bound;
			auto const resultMissing=resultBound.area()-count()-other.count();
			assert(resultMissing>=0);
			return {resultBound, resultMissing};
		}
	};
	struct Block{
		std::vector<Cover> cover;
		struct MinInfo{
			int count, value;
			MinInfo operator+(int other)const{
				if(value<other) return *this;
				if(value>other) return {1, other};
				return {count+1, value};
			}
			MinInfo operator+(MinInfo other)const{
				if(value<other.value) return *this;
				if(value>other.value) return other;
				return {count+other.count, value};
			}
		};
		std::vector<MinInfo> suffix;
		std::array<Pos, blockSize> items;
		int number;
		void build(){ // recompute necessary information after items changes
			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});
				}
			}

			suffix.resize(cover.size());
			suffix.back()={1, cover.back().missing};
			for(int pos=(int)cover.size()-1; pos--;)
				suffix[pos]=suffix[pos+1]+cover[pos].missing;
		}
		void setWithoutBuild(int index, Pos pos){
			assert(index<number);
			items[index]=pos;
		}
		std::pair<int, Cover> get(Cover const previous)const{
			int result=0;
			int lastContain=-1;
			for(int step=1<<(31^__builtin_clz((int)cover.size())); step; step>>=1)
				if(lastContain+step<(int)cover.size() and
						previous.bound.contains(cover[lastContain+step].bound))
					lastContain+=step;

			// now lastContain=last inside previous
			if(lastContain>=0 and (previous+cover[lastContain]).missing==0)
				++result;

			for(int pos=0; pos<lastContain; ++pos)
				assert((previous+cover[pos]).missing!=0);

			int pos=lastContain+1;
			while(pos<(int)cover.size()){ // this outer loop will only run for O(1) iterations
				if(cover[pos].bound.contains(previous.bound)){
					/*
					while(pos<(int)cover.size()){
						assert(
								((previous+cover[pos]).missing==0) ==
								(cover[pos].missing==previous.count())
								);
						if(cover[pos].missing==previous.count()) ++result;
						++pos;
					}
					*/
					auto const [minCount, minMissing]=suffix[pos];
					if(previous.count()==minMissing) result+=minCount;
					else assert(minMissing>previous.count());
					break;
				}

				assert(not previous.bound.contains(cover[pos].bound));
				auto const target=cover[pos].bound+previous.bound;
				auto const oldPos=pos;

				--pos;
				for(int step=1<<(31^__builtin_clz((int)cover.size())); step; step>>=1)
					if(pos+step<(int)cover.size() and
							not (cover[pos+step].bound+previous.bound).contains(target))
						pos+=step;
				assert(pos<oldPos or not (cover[pos].bound+previous.bound).contains(target));
				++pos; // now pos=first contains target after joined with previous

				for(int pos1=oldPos; pos1<pos; ++pos1)
					assert((previous+cover[pos1]).missing!=0);

				if(pos==(int)cover.size()) break;
				assert((cover[pos].bound+previous.bound).contains(target));
				if((previous+cover[pos]).missing==0) ++result;
				++pos;
			}
			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: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30