// 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);
}
