Submission #1868132

---

Source Code Expand

# 1 "code_for_submission.cpp"
#define UCHIKIRI_TIME 29000

#define NDEBUG

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <functional>
#include <set>
#include <ctime>
#include <random>
#include <chrono>
#include <cassert>
#include <tuple>
#include <utility>
using namespace std;
namespace {
using Integer = long long;
template<class T, class S> istream& operator >> (istream& is, pair<T,S>& p){return is >> p.first >> p.second;}
template<class T> istream& operator >> (istream& is, vector<T>& vec){for(T& val: vec) is >> val; return is;}
template<class T> istream& operator , (istream& is, T& val){ return is >> val;}
template<class T, class S> ostream& operator << (ostream& os, const pair<T,S>& p){return os << p.first << " " << p.second;}
template<class T> ostream& operator << (ostream& os, const vector<T>& vec){for(size_t i=0; i<vec.size(); i++) os << vec[i] << (i==vec.size()-1?"":" "); return os;}
template<class T> ostream& operator , (ostream& os, const T& val){ return os << " " << val;}
template<class H> void print(const H& head){ cout << head; }
template<class H, class ... T> void print(const H& head, const T& ... tail){ cout << head << " "; print(tail...); }
template<class ... T> void println(const T& ... values){ print(values...); cout << endl; }
template<class H> void eprint(const H& head){ cerr << head; }
template<class H, class ... T> void eprint(const H& head, const T& ... tail){ cerr << head << " "; eprint(tail...); }
template<class ... T> void eprintln(const T& ... values){ eprint(values...); cerr << endl; }
class range{ Integer start_, end_, step_; public: struct range_iterator{ Integer val, step_; range_iterator(Integer v, Integer step) : val(v), step_(step) {} Integer operator * (){return val;} void operator ++ (){val += step_;} bool operator != (range_iterator& x){return step_ > 0 ? val < x.val : val > x.val;} }; range(Integer len) : start_(0), end_(len), step_(1) {} range(Integer start, Integer end) : start_(start), end_(end), step_(1) {} range(Integer start, Integer end, Integer step) : start_(start), end_(end), step_(step) {} range_iterator begin(){ return range_iterator(start_, step_); } range_iterator end(){ return range_iterator( end_, step_); } };
inline string operator "" _s (const char* str, size_t size){ return move(string(str)); }
constexpr Integer my_pow(Integer x, Integer k, Integer z=1){return k==0 ? z : k==1 ? z*x : (k&1) ? my_pow(x*x,k>>1,z*x) : my_pow(x*x,k>>1,z);}
constexpr Integer my_pow_mod(Integer x, Integer k, Integer M, Integer z=1){return k==0 ? z%M : k==1 ? z*x%M : (k&1) ? my_pow_mod(x*x%M,k>>1,M,z*x%M) : my_pow_mod(x*x%M,k>>1,M,z);}
constexpr unsigned long long operator "" _ten (unsigned long long value){ return my_pow(10,value); }
inline int k_bit(Integer x, int k){return (x>>k)&1;}
template<class T> string join(const vector<T>& v, const string& sep){ stringstream ss; for(size_t i=0; i<v.size(); i++){ if(i>0) ss << sep; ss << v[i]; } return ss.str(); }
inline string operator * (string s, int k){ string ret; while(k){ if(k&1) ret += s; s += s; k >>= 1; } return ret; }
}
constexpr long long mod = 9_ten + 7;
namespace my_time{
# 69 "code_for_submission.cpp"
chrono::time_point<chrono::steady_clock> start_time;
void init(){
start_time = chrono::steady_clock::now();
}
long long getTime(){
return chrono::duration_cast<chrono::milliseconds>(
chrono::steady_clock::now() - start_time).count();
}
};
class XorShift{
public:
uint32_t x;
uint32_t y;
uint32_t z;
uint32_t w;
XorShift(){
x = 123456789;
y = 362436069;
z = 521288629;
w = 88675123;
}
XorShift(uint32_t seed){
x = 123456789;
y = 362436069;
z = 521288629;
w = seed;
for(int i=0; i<100; i++){
(*this)();
}
}
uint32_t next() {
uint32_t t = x ^ (x << 11);
x = y; y = z; z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
uint32_t operator () () {
return next();
}

int operator () (int range){
return next()%range;
}

double prob(){
return (next()&0xfffffff) * 3.7252903123397e-9;
}
int pp(){
return next()&0x7FFFFFFF;
}
};
XorShift x_rand(114514);
mt19937 mt(114514);
#include <vector>
#include <sstream>
#include <random>
#include <cstdio>
#include <cassert>
#include <vector>
#include <set>
#include <utility>
#include <algorithm>
#include <random>
#include <numeric>
class Generator{
public:
int buffer_len = 0;
char buffer[500000];


const int MIN_V = 2;
const int MAX_V = 500;
const int MIN_E = 1;
const int MAX_E = 20000;

const int MIN_N = 2;
const int MAX_N = 60;

#ifndef RANDGEN
#define RANDGEN 
struct Rand {
public:
Rand() = default;
Rand(std::mt19937_64::result_type seed_input) : mt(seed_input) {}
int NextInt(int a, int b) {
return std::uniform_int_distribution<int>{a, b}(mt);
}
private:
std::mt19937_64 mt{std::random_device{}()};
};
#endif

void gen_kingsgraph(int N) {

int V = N * N;
int E = 4*N*N - 6*N + 2;
buffer_len += sprintf(buffer + buffer_len, "%d %d\n", V, E);
return;



int dx1[] = {0, 0, 0, 0};
int dy1[] = {0, 0, 0, 1};
int dx2[] = {0, 1, 1, 1};
int dy2[] = {1, 0, 1, 0};
for(int i=0; i<N-1; i++) {
for(int j=0; j<N-1; j++) {
int current_v = i*N + (j+1);
for(int k=0; k<4; k++) {
int start_v = current_v + dx1[k]*N + dy1[k];
int goal_v = current_v + dx2[k]*N + dy2[k];
if(start_v > goal_v) std::swap(start_v, goal_v);
buffer_len += sprintf(buffer + buffer_len, "%d %d\n", start_v, goal_v);
}
}
}

for(int i=0; i<N-1; i++) {
int start_v = (i+1) * N;
int goal_v = (i+2) * N;
buffer_len += sprintf(buffer + buffer_len, "%d %d\n", start_v, goal_v);
}

for(int i=0; i<N-1; i++) {
int start_v = (N-1)*N + (i+1);
int goal_v = start_v + 1;
buffer_len += sprintf(buffer + buffer_len, "%d %d\n", start_v, goal_v);
}
}

void gen_randomgraph(int V, int E, unsigned long long int seed) {
Rand rnd_random(seed);
assert(V - 1 <= E && E <= V * (V-1) / 2);
buffer_len += sprintf(buffer + buffer_len, "%d %d\n", V, E);

std::mt19937_64 engine(seed);
std::vector<int> func(V);
std::iota(func.begin(), func.end(), 1);
std::shuffle(func.begin(), func.end(), engine);
std::set< std::pair<int, int> > edges;
for(int i=1; i<V; i++) {
int parent = rnd_random.NextInt(0, i-1);
int u = func[i], v = func[parent];
if(u > v) std::swap(u, v);
buffer_len += sprintf(buffer + buffer_len, "%d %d\n", u, v);
edges.insert( std::make_pair(u, v) );
}
for(int i=0; i<E-(V-1); i++) {
while(1) {
int u = rnd_random.NextInt(1, V);
int v = rnd_random.NextInt(1, V);
if(u == v) continue;
if(u > v) std::swap(u, v);

if(edges.count( std::make_pair(u, v) ) != 0) continue;
edges.insert( std::make_pair(u, v) );
buffer_len += sprintf(buffer + buffer_len, "%d %d\n", u, v);
break;
}
}
}

unsigned long long int str2ull(char *str) {
char* end_point;
unsigned long long int ret_number = strtoull(str, &end_point, 10);
if(*end_point != '\0') {
fprintf(stderr, "Error: invalid input: \"%s\"\n", str);
exit(1);
}
return ret_number;
}
int main(unsigned long long seed) {

Rand rnd(seed);
int V = rnd.NextInt(MIN_V, MAX_V);
int E = rnd.NextInt(V-1, std::min(V*(V-1)/2, MAX_E));
gen_randomgraph(V, E, seed);
int N;
while(1) {
N = rnd.NextInt(MIN_N, MAX_N);
if(N*N >= V) break;
}
gen_kingsgraph(N);
return 0;
}
};




#ifdef GENERATE
#include <iostream>
int main(){
unsigned long long seed;
std::cin >> seed;
Generator g;
g.main(seed);
std::cout << g.buffer << std::endl;
return 0;
}
#endif
#ifndef MYBITSET
#define MYBITSET 
struct MyBitset{

unsigned long long arr[10];
int len;
int packs;
int cnt;
MyBitset(int l) : len(l), packs( (l+63)>>6 ), cnt(0) {
for(int i=0; i<packs; i++){
arr[i] = 0;
}
}
MyBitset(const MyBitset& c) : len(c.len), packs(c.packs), cnt(c.cnt) {
for(int i=0; i<packs; i++){
arr[i] = c.arr[i];
}
}
int pop_count(){
int res = 0;
int i=0;
for(; i+1<packs; i+=2){
res += __builtin_popcountll(arr[i]) + __builtin_popcountll(arr[i+1]);
}
for(; i<packs; ++i){
res += __builtin_popcountll(arr[i]);
}
cnt = res;
return cnt;
}
MyBitset operator& (const MyBitset& c){
MyBitset res(this->len);
int i = 0;
for(; i+1<packs; i+=2){
res.arr[i ] = arr[i ]&c.arr[i ];
res.arr[i+1] = arr[i+1]&c.arr[i+1];
}
for(; i<packs; ++i){
res.arr[i ] = arr[i ]&c.arr[i ];
}
res.cnt = res.pop_count();
return res;
}
MyBitset operator| (const MyBitset& c){
MyBitset res(this->len);
int i = 0;
for(; i+1<packs; i+=2){
res.arr[i ] = arr[i ]|c.arr[i ];
res.arr[i+1] = arr[i+1]|c.arr[i+1];
}
for(; i<packs; ++i){
res.arr[i ] = arr[i ]|c.arr[i ];
}
res.cnt = res.pop_count();
return res;
}
void operator&= (const MyBitset& c){
int i = 0;
for(; i+1<packs; i+=2){
arr[i] &= c.arr[i];
arr[i+1] &= c.arr[i+1];
}
for(; i<packs; ++i){
arr[i] &= c.arr[i];
}
cnt = pop_count();
}
void operator|= (const MyBitset& c){
int i = 0;
for(; i+1<packs; i+=2){
arr[i] |= c.arr[i];
arr[i+1] |= c.arr[i+1];
}
for(; i<packs; ++i){
arr[i] |= c.arr[i];
}
cnt = pop_count();
}
bool operator == (const MyBitset& c){
if(this->cnt != c.cnt) return false;
for(int i=0; i<packs; i++){
if( arr[i] != c.arr[i] ) return false;
}
return true;
}
void set(int at, bool value){
int p = at>>6;
int k = at&63;
if(value){
if( (~arr[p]>>k)&1 ){
arr[p] ^= 1ull<<k;
cnt++;
}
}else{
if( (arr[p]>>k)&1 ){
arr[p] ^= 1ull<<k;
cnt--;
}
}
}
bool get(int at){
int p = at>>6;
int k = at&63;
return (arr[p]>>k)&1;
}
int size(){
return cnt;

}
};
ostream& operator << (ostream& os, MyBitset& b){
for(int i=0; i<b.len; i++){
os << (b.get(i)?1:0);
}
return os;
}
#endif



namespace TestCase{
using namespace std;
vector<vector<bool>> G;
vector<vector<uint16_t>> E;
vector<pair<uint16_t,uint16_t>> Edge;
int V;
int Vemb;
vector<MyBitset> Mask;
void set_mask(){
Mask = vector<MyBitset>(V, MyBitset(V));
for(int i=0; i<V; i++){
for(auto j : E[i]){
Mask[i].set(j, true);
}
}
}



void input(){
int v,e;
scanf("%d%d", &v,&e);
V = v;
G = vector<vector<bool>>(V, vector<bool>(V, 0));
E = vector<vector<uint16_t>>(V);
Edge = {};
for(int i=0; i<e; i++){
int x,y;
scanf("%d%d", &x,&y);
x--; y--;
G[x][y] = 1;
G[y][x] = 1;
E[x].push_back(y);
E[y].push_back(x);
Edge.push_back( {x,y} );
}
int vemb;
scanf("%d", &vemb);
Vemb = sqrt(vemb);
set_mask();
}



void generate(unsigned long long seed){
Generator g;
g.main(seed);
stringstream ss(g.buffer);
int v,e;
ss >> v >> e;
V = v;
G = vector<vector<bool>>(V, vector<bool>(V, 0));
E = vector<vector<uint16_t>>(V);
Edge = {};
for(int i=0; i<e; i++){
int x,y;
ss >> x >> y;
x--; y--;
G[x][y] = 1;
G[y][x] = 1;
E[x].push_back(y);
E[y].push_back(x);
Edge.push_back( {x,y} );
}
int vemb;
ss >> vemb;
Vemb = sqrt(vemb);
set_mask();
}
}
#include <fstream>
class Visualizer{
public:
vector<vector<int>> res;
void push( vector<vector<int>>& S ){
#ifdef VIS
res.push_back({});
for(int i=0; i<S.size(); i++){
for(int j=0; j<S[i].size(); j++){
res.back().push_back(i);
res.back().push_back(S[i][j]);
}
}
#endif
}
void push( vector<deque<int>>& S ){
#ifdef VIS
res.push_back({});
for(int i=0; i<S.size(); i++){
for(int j=0; j<S[i].size(); j++){
res.back().push_back(i);
res.back().push_back(S[i][j]);
}
}
#endif
}
void pop(){
#ifdef VIS
if(res.size()) res.pop_back();
#endif
}
~Visualizer(){
#ifdef VIS
ofstream ofs("result.txt");
ofs << res.size() << endl;
for(int i=0; i<res.size(); i++){
for(int j=0; j<res[i].size(); j++){
if(j) ofs << " ";
ofs << res[i][j];
}
ofs << endl;
}
#endif
}
};
Visualizer vis;
#ifndef INITARRAY
#define INITARRAY 
#include <map>




template<size_t D, class T>
class InitializedArray{
public:

T A[D];
int E[D];
int epoch = 0;
T defaultValue;
InitializedArray(T d){
defaultValue = d;
for(size_t i=0; i<D; i++){

A[i] = d;
}
}
void init(){
epoch++;
}
T& operator[](size_t idx){



if(E[idx] != epoch){
E[idx] = epoch;
A[idx] = defaultValue;
}

return A[idx];
}
};
#endif
#ifdef INITARRAY_TEST
#include <iostream>
using namespace std;
int main(){
InitializedArray<10, int> arr(-1);
for(int i=0; i<10; i++){
arr[i] = i;
cout << arr[i] << " ";
}
cout << endl;
arr.init();
for(int i=0; i<10; i++){
cout << arr[i] << " ";
arr[i] = i+1;
}
cout << endl;
arr.init();
for(int i=0; i<10; i++){
cout << arr[i] << " ";
}
cout << endl;
for(int i=0; i<10; i++){
arr[i] = i + 8;
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
#endif
namespace Util{
using namespace TestCase;
int dx[] = {
-1, 0,+1,
-1, +1,
-1, 0,+1
};
int dy[] = {
-1,-1,-1,
0, 0,
+1,+1,+1
};
int dx4[] = {
0,
-1, +1,
0
};
int dy4[] = {
-1,
0, 0,
+1
};
int dxd[] = {
-1, +1,
-1, +1
};
int dyd[] = {
-1, -1,
+1, +1
};

int dyx[] = {
-1,-1,+1,+1,-1,+0,+0,+1
};
int dxx[] = {
-1,+1,-1,+1,+0,-1,+1,+0
};

int dyr[] = {
1,1,0,1
};
int dxr[] = {
1,-1,1,0
};



vector<int> px,py;
void set_pxpy(){
px.resize(Vemb*Vemb);
py.resize(Vemb*Vemb);
for(int i=0; i<Vemb; i++){
for(int j=0; j<Vemb; j++){
px[i*Vemb + j] = j;
py[i*Vemb + j] = i;
}
}
}
int get_pos(int y, int x){
return y*Vemb + x;
}
int get_x(int pos){

return px[pos];
}
int get_y(int pos){

return py[pos];
}
bool out_of_bounds(int y, int x){
return (y<0 || y>=Vemb || x<0 || x>=Vemb);
}




void output(vector<vector<int>>& res){
for(int i=0; i<TestCase::V; i++){
printf("%d", res[i].size());
for(int j=0; j<res[i].size(); j++){
printf(" %d", res[i][j]+1);
}
printf("\n");
}
}
template<class T>
void shuffle(vector<T>& v){
int n = v.size();
for(int i=n-1; i>0; i--){
int j = x_rand(i);
swap(v[i], v[j]);
}
}
int calcScore(const vector<vector<int>>& mapper){
static InitializedArray<3600, int16_t> field(-1);
field.init();
for(int i=0; i<V; i++){
assert( mapper[i].size() );
for(int pos : mapper[i] ){
field[ pos ] = i;
}
}
static InitializedArray<500*500, char> conn(0);
conn.init();
int numValidEdge = 0;
int numUsedVertex = 0;
for(int i=0; i<V; i++){
for(int pos : mapper[i] ){
numUsedVertex++;
int y = get_y(pos);
int x = get_x(pos);
for(int k=0; k<8; k++){
int yy = y + dy[k];
int xx = x + dx[k];
if( out_of_bounds(yy,xx) ) continue;
int a_pos = get_pos(yy,xx);
int w = field[a_pos];
if( w==-1 || w==i ) continue;
if( conn[i*V + w] || G[i][w] == 0 ) continue;
numValidEdge++;
conn[i*V + w] = 1;
conn[w*V + i] = 1;
}
}
}
int score = 5000;
score += numValidEdge * 100;
score -= numUsedVertex - V;
if( numValidEdge == Edge.size() ){
score += 100000;
}
return score;
}
}
#ifndef MYLIST
#define MYLIST 
#include <algorithm>
#include <cassert>


template<size_t D>
class MyList{
public:
int P[D];
int P_inv[D];
int cnt = 0;
MyList(){
fill(std::begin(P_inv), std::end(P_inv), -1);
}

void clear(){

for(int i=0; i<cnt; i++){
P_inv[ P[i] ] = -1;
}
cnt = 0;
}
void insert(int value){


if( P_inv[value] != -1 ) return;
P[cnt] = value;
P_inv[ value ] = cnt;
cnt++;
}
void erase(int value){

if( P_inv[value] == -1 ) return;
int i = P_inv[value];
int j = cnt-1;
P_inv[ P[j] ] = i;
P_inv[ P[i] ] = -1;
std::swap( P[i], P[j] );
cnt--;
}



int pop(){
int i = cnt-1;
int value = P[ i ];
P_inv[value] = -1;
cnt--;
return value;
}



int random_pick(){
assert( cnt > 0 );
int i = x_rand(cnt);
return P[i];
}
int size(){
return cnt;
}
bool has_key(int value){
return P_inv[value] != -1;
}
struct iterator{
int pos;
int *P;
int operator*(){
return P[pos];
}
void operator ++ (){
pos++;
}
bool operator != (iterator& x){
return this->pos != x.pos;
}
};
iterator begin(){
return iterator{0, P};
}
iterator end(){
return iterator{cnt, P};
}
void swap(MyList& a){
for(int i=0; i<cnt; i++){
P_inv[ P[i] ] = -1;
}
for(int i=0; i<a.cnt; i++){
a.P_inv[ a.P[i] ] = -1;
}
int k = max(cnt, a.cnt);
for(int i=0; i<k; i++){
std::swap(P[i], a.P[i]);
}
std::swap(cnt, a.cnt);
for(int i=0; i<cnt; i++){
P_inv[ P[i] ] = i;
}
for(int i=0; i<a.cnt; i++){
a.P_inv[ a.P[i] ] = i;
}
}
};
template<size_t D, class T>
class RandomQue{
public:
T P[D];
int cnt = 0;
RandomQue(){}
void push(T value){


P[cnt] = value;
cnt++;
}
T pop(){
assert(cnt > 0);
int i = x_rand(cnt);
int j = cnt-1;
T ret = P[i];
swap( P[i], P[j] );
cnt--;
return ret;
}
int size(){
return cnt;
}
void init(){
cnt = 0;
}
struct iterator{
int pos;
T* P;
T operator*(){
return P[pos];
}
void operator ++ (){
pos++;
}
bool operator != (iterator& x){
return this->pos != x.pos;
}
};
iterator begin(){
return iterator{0, P};
}
iterator end(){
return iterator{cnt, P};
}
};
# 878 "code_for_submission.cpp"
#endif
#ifndef MYQUEUE
#define MYQUEUE 
template<size_t D, class T>
class MyQueue{
public:
T arr[D];
int head = 0;
int tail = 0;
void init(){
head = tail = 0;
}
void push(T val){
arr[tail++] = val;
assert(tail<=D);
}
T pop(){
assert( size() > 0 );
return arr[head++];
}
T peek(){
assert( size() > 0 );
return arr[head];
}
T pop_back(){
assert( size() > 0 );
return arr[--tail];
}
T peek_back(){
assert( size() > 0 );
return arr[tail-1];
}
size_t size(){
return tail - head;
}
};
template<class T>
class FastPriorityQueue_2Layer{
public:
const int D = 64*64;
deque<T> Q[ 64*64 ];
unsigned long long parent_dict;
unsigned long long child_dict[64];
FastPriorityQueue_2Layer() : parent_dict(0ll) {
fill(child_dict, child_dict+64, 0ll);
}
void clear(){
while( parent_dict != 0 ){
int p = __builtin_ffsll(parent_dict) - 1;
child_dict[p] = 0;
parent_dict ^= 1ull << p;
}
}
void hard_reset(){
while( parent_dict != 0 ){
int p = __builtin_ffsll(parent_dict) - 1;
while( child_dict[p] != 0 ){
int c = __builtin_ffsll(child_dict[p]) - 1;
int key = (p<<6) + c;
Q[key].resize(0);
child_dict[p] ^= 1ull << c;
}
parent_dict ^= 1ull << p;
}
}
void push(int key, T value){
if( key >= D ) return;
int p_key = key >> 6;
int c_key = key & 63;
if( (~child_dict[p_key] >> c_key)&1 ){
if(Q[key].size() > 0){
Q[key].resize(0);
}
}
Q[key].push_back( value );
child_dict[p_key] |= 1ull << c_key;
parent_dict |= 1ull << p_key;
}


pair<int,T> pop(){
assert( parent_dict > 0 );
int p_key = __builtin_ffsll(parent_dict) - 1;
int c_key = __builtin_ffsll(child_dict[p_key]) - 1;
assert(c_key >= 0);
int key = (p_key<<6) + c_key;
auto& q = Q[key];
int i = x_rand(q.size());

auto res = q[i];
swap(q[i], q.back());
q.pop_back();
if( q.size() == 0 ){
child_dict[p_key] ^= 1ull << c_key;
if( child_dict[p_key] == 0 ){
parent_dict ^= 1ull << p_key;
}
}
return {key, res};
}
bool empty(){
return parent_dict == 0;
}
};
#endif
namespace RandomSolver{
using namespace TestCase;
using namespace Util;
pair<int, vector<vector<int>>> solve(){
static RandomQue<3600, int> emptyCell;
emptyCell.init();
for(int i=0; i<Vemb*Vemb; i++){
emptyCell.push(i);
}
vector<int> field(Vemb*Vemb, -1);
vector<vector<bool>> connected(V, vector<bool>(V, false));
int connectedEdgeCnt = 0;
vector<vector<int>> res(V);
for(int i=0; i<V; i++){
int p = emptyCell.pop();
res[i].push_back(p);
field[p] = i;
int y = get_y(p);
int x = get_x(p);
for(int k=0; k<8; k++){
int yy = y + dy[k];
int xx = x + dx[k];
if( out_of_bounds(yy,xx) ) continue;
int pp = get_pos(yy,xx);
int j = field[pp];
if( j != -1 && G[i][j] && connected[i][j] == false){
connected[i][j] = connected[j][i] = true;
connectedEdgeCnt++;
}
}
}
static RandomQue<20000, int> edge_same[2];
static RandomQue<20000, int> edge_diff[2];
static RandomQue<20000, int> edge_skipped[2];
edge_same[0].init();
edge_same[1].init();
edge_diff[0].init();
edge_diff[1].init();
edge_skipped[0].init();
edge_skipped[1].init();
for(int i=0; i<Edge.size(); i++){
int u,v;
u = Edge[i].first;
v = Edge[i].second;
if( (get_y(res[u][0])+get_x(res[u][0]))%2 == (get_y(res[v][0])+get_x(res[v][0]))%2 ){
edge_same[0].push( i );
}else{
edge_diff[0].push( i );
}
}
static InitializedArray<3600, int> dist1(1e6), dist2(1e6);
static MyQueue<10000, int> Q[2];
int ddd[] = {3,4,5,6,10,128};
for(int t=0; t<=2; t++)
for(int kkk=0; kkk<6; kkk++){

auto& ee = (t==0 ? edge_same[kkk&1]: t==1 ? edge_diff[kkk&1] : edge_skipped[kkk&1]);
while( ee.size() ){
int e = ee.pop();
int u = Edge[e].first;
int v = Edge[e].second;
if( connected[u][v] ) continue;
Q[0].init();
Q[1].init();
dist1.init();
dist2.init();
for(auto p : res[u]){
dist1[p] = 0;
Q[0].push(p);
}
for(auto p : res[v]){
dist2[p] = 0;
Q[1].push(p);
}
int j0 = -1, j1 = -1;
for(int dd=0; dd<ddd[kkk] && j0==-1 && j1==-1 && Q[0].size() && Q[1].size(); dd++){
while( Q[0].size() && dist1[ Q[0].peek() ] == dd && j0 == -1){
int p = Q[0].pop();
int y = get_y(p);
int x = get_x(p);
for(int k=0; k<(t<2?4:8); k++){
int yy = y + (t<2?dyd[k]:dy[k]);
int xx = x + (t<2?dxd[k]:dx[k]);
if( out_of_bounds(yy,xx) ) continue;
int pp = get_pos(yy,xx);
if( dist2[pp] <= dd+1 ){
j0 = p;
j1 = pp;
break;
}
if( field[pp] != -1 ){
continue;
}else{
if( dist1[pp] > dd+1 ){
dist1[pp] = dd+1;
Q[0].push(pp);
}
}
}
}
while( Q[1].size() && dist2[ Q[1].peek() ] == dd && j1 == -1){
int p = Q[1].pop();
int y = get_y(p);
int x = get_x(p);
for(int k=0; k<(t<2?4:8); k++){
int yy = y + (t<2?dyd[k]:dy[k]);
int xx = x + (t<2?dxd[k]:dx[k]);
if( out_of_bounds(yy,xx) ) continue;
int pp = get_pos(yy,xx);
if( dist1[pp] <= dd+1 ){
j0 = pp;
j1 = p;
break;
}
if( field[pp] != -1 ){
continue;
}else{
if( dist2[pp] > dd+1 ){
dist2[pp] = dd+1;
Q[1].push(pp);
}
}
}
}
}
if( j0 == -1 ){
if( kkk==5 ){
if(t<2) edge_skipped[0].push( e );
}else{
auto& ee_ = (t==0 ? edge_same[~kkk&1] : t==1 ? edge_diff[~kkk&1] : edge_skipped[~kkk&1] );
ee_.push( e );
}
continue;
}

while(true){
int dd = dist1[j0];
if( dd == 0 ) break;
res[u].push_back( j0 );
field[j0] = u;
int y = get_y(j0);
int x = get_x(j0);
int kk = x_rand(4);
for(int k=0; k<(t<2?4:8); k++){
int yy = y + (t<2?dyd[(k+kk)%4]:dy[(k+kk)%8]);
int xx = x + (t<2?dxd[(k+kk)%4]:dx[(k+kk)%8]);
if( out_of_bounds(yy,xx) ) continue;
int pp = get_pos(yy,xx);
if( dist1[pp] < dist1[j0] ){
j0 = pp;
break;
}
}
for(int k=0; k<8; k++){
int yy = y + dy[k];
int xx = x + dx[k];
if( out_of_bounds(yy,xx) ) continue;
int pp = get_pos(yy,xx);
int w = field[pp];
if( w != -1 && G[u][w] && connected[u][w] == false){
connected[u][w] = connected[w][u] = true;
connectedEdgeCnt++;
}
}
}

while(true){
int dd = dist2[j1];
if( dd == 0 ) break;
res[v].push_back( j1 );
field[j1] = v;
int y = get_y(j1);
int x = get_x(j1);
int kk = x_rand(4);
for(int k=0; k<(t<2?4:8); k++){
int yy = y + (t<2?dyd[(k+kk)%4]:dy[(k+kk)%8]);
int xx = x + (t<2?dxd[(k+kk)%4]:dx[(k+kk)%8]);
if( out_of_bounds(yy,xx) ) continue;
int pp = get_pos(yy,xx);
if( dist2[pp] < dist2[j1] ){
j1 = pp;
break;
}
}
for(int k=0; k<8; k++){
int yy = y + dy[k];
int xx = x + dx[k];
if( out_of_bounds(yy,xx) ) continue;
int pp = get_pos(yy,xx);
int w = field[pp];
if( w != -1 && G[v][w] && connected[v][w] == false){
connected[v][w] = connected[w][v] = true;
connectedEdgeCnt++;
}
}
}
}

}

int score = 5000;
score += connectedEdgeCnt * 100;
if(connectedEdgeCnt == Edge.size()) score += 100000;
for(int i=0; i<V; i++){
score -= res[i].size()-1;
}
return {score, res};
}
}

class State{
public:



vector<int16_t> field;



vector<MyBitset> Conn;




vector<vector<int>> mapper;




vector<MyList<500>> adj;



vector<uint16_t> validConnection;

int numValidEdge;

int numUsedVertex;
int score;
int calc_score(){







int res = 5000;
res += 100 * numValidEdge;
res -= numUsedVertex - TestCase::V;
if( numValidEdge == TestCase::Edge.size() ){



}
return res;
}





int swap(int u, int v){
using namespace Util;
static int a[2][510];
vector<int> cnt = {adj[u].size(), adj[v].size()};
for(int k=0; k<2; k++)
for(int i=0; i<cnt[k]; i++){
a[k][i] = adj[k==0?u:v].P[i];
}
int prevValidEdge = numValidEdge;

for(int k=0; k<2; k++){
int z = k==0 ? u : v;
for(int i=0; i<cnt[k]; i++){
int w = a[k][i];

if( adj[z].has_key(w) == false ){
assert( (z==u && w==v) || (z==v && w==u) );
continue;
}
if( G[z][w] ){
numValidEdge--;
validConnection[z]--;
validConnection[w]--;
}
adj[z].erase(w);
adj[w].erase(z);
Conn[z].set(w, false);
Conn[w].set(z, false);
}
}

for(int k=0; k<2; k++){
int z = k==0 ? v : u;
for(int i=0; i<cnt[k]; i++){
int w = a[k][i];

if( z == w ) w = (z^u^v);
if( adj[z].has_key(w) == true ){
assert( (z==u && w==v) || (z==v && w==u) );
continue;
}
if( G[z][w] ){
numValidEdge++;
validConnection[z]++;
validConnection[w]++;
}
adj[z].insert(w);
adj[w].insert(z);
Conn[z].set(w, true);
Conn[w].set(z, true);
}
}
std::swap(mapper[u], mapper[v]);
# 1310 "code_for_submission.cpp"
score = calc_score();
return score;
}



int get_swap_score(int u, int v){
using namespace Util;
int s = score - numValidEdge*100;
int e = numValidEdge;
e -= (Conn[u]&Mask[u]).size();
e -= (Conn[v]&Mask[v]).size();
e += (Conn[v]&Mask[u]).size();
e += (Conn[u]&Mask[v]).size();
if( adj[u].has_key(v) && G[u][v] ){
e += 2;
}
return s + e*100;
}
int swap_fast(int u, int v){
using namespace Util;
int s = score - numValidEdge*100;
int& e = numValidEdge;
e -= (Conn[u]&Mask[u]).size();
e -= (Conn[v]&Mask[v]).size();
e += (Conn[v]&Mask[u]).size();
e += (Conn[u]&Mask[v]).size();
if( adj[u].has_key(v) && G[u][v] ){
e += 2;
}
s = s + e*100;
for(auto z : vector<int>{u,v}){
for(auto w : adj[z]){
if( w==u || w==v ) continue;
bool a = Conn[w].get(u);
bool b = Conn[w].get(v);
if( a&&b ) continue;
Conn[w].set(u, b);
Conn[w].set(v, a);
if(a){
adj[w].erase(u);
adj[w].insert(v);
}else{
adj[w].erase(v);
adj[w].insert(u);
}
}
}
if(adj[u].has_key(v))
for(auto w : vector<int>{u,v}){
bool a = Conn[w].get(u);
bool b = Conn[w].get(v);
Conn[w].set(u, b);
Conn[w].set(v, a);
if(a){
adj[w].erase(u);
adj[w].insert(v);
}else{
adj[w].erase(v);
adj[w].insert(u);
}
}
adj[u].swap( adj[v] );
std::swap( Conn[u], Conn[v] );

std::swap(mapper[u], mapper[v]);
score = s;
return score;
}





int init(vector<vector<int>>& mapper_){
using namespace Util;
field = vector<int16_t>(Vemb * Vemb, -1);
Conn = vector<MyBitset>(V, MyBitset(V));
mapper = mapper_;
int n = V;
adj = vector<MyList<500>>(n);
for(int i=0; i<n; i++){
adj[i].clear();
}
validConnection = vector<uint16_t>(n, 0);
numValidEdge = 0;
numUsedVertex = 0;
for(int i=0; i<n; i++){
for(auto pos : mapper[i]){
field[pos] = i;
numUsedVertex++;
}
}
for(int v=0; v<n; v++){
for(auto pos : mapper[v]){
int y = get_y(pos);
int x = get_x(pos);
for(int k=0; k<8; k++){
int yy = y + dy[k];
int xx = x + dx[k];
if( out_of_bounds(yy,xx) ) continue;
int a_pos = get_pos(yy,xx);
int w = field[a_pos];
if( w == -1 || w == v ) continue;
Conn[v].set(w, true);
Conn[w].set(v, true);
adj[v].insert(w);
adj[w].insert(v);
}
}
}
for(int v=0; v<n; v++){
auto tmp = Conn[v] & Mask[v];
numValidEdge += tmp.cnt;
validConnection[v] = tmp.cnt;
# 1435 "code_for_submission.cpp"
}
numValidEdge /= 2;
score = calc_score();
return score;
}
};
namespace SA{
using namespace Util;
bool accept(int diff, int t){
if(diff >= 0) return true;

double T = max( 2.1, - t * 30e-8 + 4.0 );
double w = diff / T;

constexpr double a = 0.10;
if( -w*a > 31.5 ) return false;
long long k = 31.5 + w*a;
long long x = 1ull << k;
return x_rand.pp() < x;


}





pair<int, vector<vector<int>>> SA(vector<vector<int>>& mapper_, int numItr = 1600000, int resetItr = -1){
auto best_mapper = mapper_;
State s;
int best_score = s.init(best_mapper);
vector<uint16_t> perm(V);
iota(perm.begin(), perm.end(), 0);
vector<uint16_t> best_perm = perm;
int forced_update = 0;
int unforced_update = 0;
int best_update = 0;
static int tt = 0;
if( resetItr != -1){
tt = resetItr;
}

for(int t=0; t<numItr; t++, tt++){
if( (t&0x3FFFF) == 0){
if( my_time::getTime() > UCHIKIRI_TIME ){
break;
}
}
int prev_score = s.score;
int u = x_rand(V);

int v;
if( (x_rand()&1023) < 1000){
v = E[u][ x_rand(E[u].size()) ];
if( s.adj[v].size() ){
v = s.adj[v].random_pick();
}
if( s.adj[u].has_key(v) && (x_rand()&1023) < 512 ){
v = x_rand(V);
}
}else{
v = x_rand(V);
}
if(u == v) continue;


int next_score = s.get_swap_score(u,v);
int diff = next_score - prev_score;




if( accept(diff, tt) ){


int nx_s = s.swap(u,v);

if( diff >= 0 ){
unforced_update++;
}else{
forced_update++;
}
swap( perm[u], perm[v] );
if( next_score > best_score ){

best_update++;
best_score = next_score;

best_perm = perm;

}
}else{

assert( s.score == prev_score );
}
}
for(int i=0; i<V; i++){
best_mapper[i] = mapper_[ best_perm[i] ];
}
return {best_score, best_mapper};
}
}




namespace Remover{
using namespace Util;
InitializedArray<3600, int> field(-1);

vector<MyBitset> set_adj(int i, vector<int>& s){
int m = s.size();
vector<MyBitset> adj(m, MyBitset(V));
for(int j=0; j<m; j++){
int pos = s[j];
int y = get_y(pos);
int x = get_x(pos);
for(int k=0; k<8; k++){
int yy = y + dy[k];
int xx = x + dx[k];
if( out_of_bounds(yy,xx) ) continue;
int a_pos = get_pos(yy,xx);
int w = field[a_pos];
if( w == -1 || w == i ) continue;
adj[j].set(w, true);
}
}
return move(adj);
}
char isArticulationPoint[3600];
int ord[3600];
int low[3600];
InitializedArray<3600, int> visited(0);
int lowlink_dfs(int pos, int par, int& t, int s){
int ch = 0;
int max_low = -1;
ord[pos] = t++;
low[pos] = ord[pos];
visited[pos] = 1;
int y = get_y(pos);
int x = get_x(pos);
for(int k=0; k<8; k++){
int yy = y + dy[k];
int xx = x + dx[k];
if( out_of_bounds(yy,xx) ) continue;
int a_pos = get_pos(yy,xx);
int w = field[a_pos];
if( w != s ) continue;

if( !visited[a_pos] ){
max_low = max(max_low, lowlink_dfs(a_pos, pos, t, s));
low[pos] = min(low[pos], low[a_pos]);
ch++;
}else{

low[pos] = min(low[pos], ord[a_pos]);
}
}
if(par==-1){
isArticulationPoint[pos] = ch > 1 ? 1 : 0;
}else{
isArticulationPoint[pos] = ord[pos] <= max_low ? 1 : 0;
}
return low[pos];
}





void lowlink(int s, int root){
visited.init();
int t = 0;
lowlink_dfs(root, -1, t, s);
}
vector<vector<int>> remove(vector<vector<int>> mapper){

field.init();

static FastPriorityQueue_2Layer<int> pq;
pq.clear();
for(int i=0; i<V; i++){
int d = 3600 - mapper[i].size();
pq.push(d , i);
for(int pos : mapper[i]){
field[pos] = i;
}
}
int numRemoved = 0;
for(int t=0; t<V; t++){
int i = pq.pop().second;
auto& s = mapper[i];
int m = s.size();
if(m==0) continue;
shuffle(s);

auto adj = set_adj(i, s);
MyBitset adj_all(V);
for(int j=0; j<m; j++){
adj_all |= adj[j];
}


vector<MyBitset> adj_r(m, MyBitset(V));
for(int j=m-2; j>=0; j--){
adj_r[j] = adj_r[j+1] | adj[j+1];
}

auto valid_adj = adj_all & Mask[i];



MyBitset adj_l(V);
bool update = false;
for(int j=0; j<m; j++){
visited.init();
int pos = s[j];
if( field[pos] != i ){
}
assert( field[pos] == i );
if(j==0 || update){
lowlink(i, pos);
update = false;
}
if( isArticulationPoint[pos] ){

if( x_rand(1024) < 100 ){
vector<int> a;
vector<int> e;
int y = get_y(pos);
int x = get_x(pos);
for(int k=0; k<8; k++){
int yy = y + dy[k];
int xx = x + dx[k];
if(out_of_bounds(yy,xx)) continue;
int a_pos = get_pos(yy,xx);
if( field[a_pos] == -1 ){
e.push_back(a_pos);
}else if( field[a_pos] == i ){
a.push_back(a_pos);
}
}
bool moved = false;
for(int np : e){
assert( field[np] == -1 );
int y_ = get_y(np);
int x_ = get_x(np);
vector<int> b;
MyBitset f(V);
for(int k=0; k<8; k++){
int yy = y_ + dy[k];
int xx = x_ + dx[k];
if(out_of_bounds(yy,xx)) continue;
int a_pos = get_pos(yy,xx);

int w = field[a_pos];
if( w == i ){
b.push_back(a_pos);
}else if( w != -1 ){
f.set( w, true );
}
}
if( b.size() < a.size() ) continue;
int ok = true;
for(int z : a){
ok = ok && (count(b.begin(), b.end(), z) > 0);
}
if(!ok) continue;
auto nx_adj = (adj_l | adj_r[j] | f) & Mask[i];
if( (nx_adj&valid_adj) == valid_adj ){
valid_adj = nx_adj;
adj[j] = f;
assert(field[pos] == i);
assert(field[np] == -1);

field[pos] = -1;
field[np] = i;
s[j] = np;

update = true;
moved = true;
break;
}
}
adj_l |= adj[j];
continue;
}else{
adj_l |= adj[j];
continue;
}
continue;
}


auto nx_adj = (adj_l | adj_r[j]) & Mask[i];
if( nx_adj == valid_adj ){


update = true;
assert( field[pos] == i );
field[pos] = -1;
s[j] = -1;
}else{

adj_l |= adj[j];
}
}
vector<int> res;
for(int j=0; j<m; j++){
if( s[j] == -1 ){
numRemoved++;
continue;
}
if( field[s[j]] == i ){
res.push_back( s[j] );
}else{
assert( field[s[j]] == -1 );
numRemoved++;
}
}
s = res;

}

return move(mapper);
}
}



namespace Remapper{
using namespace Util;
InitializedArray<3600, int16_t> field(-1);
InitializedArray<3600, char> checked(0);

MyBitset get_adj(int start, vector<uint16_t>& s){
MyBitset adj(V);
static MyQueue<10000, uint16_t> q;
q.init();
q.push(start);
checked[start] = 1;
while(q.size()){
int pos = q.pop();
s.push_back(pos);
int y = get_y(pos);
int x = get_x(pos);
for(int k=0; k<8; k++){
int yy = y + dy[k];
int xx = x + dx[k];
if( out_of_bounds(yy,xx) ) continue;
int a_pos = get_pos(yy,xx);
int w = field[a_pos];
if( w == -1 ){
if( checked[a_pos] == 0 ){
checked[a_pos] = 1;
q.push(a_pos);
}
}else{
adj.set(w, true);
}
}
}
return adj;
}

void remap(vector<vector<int>>& mapper){

checked.init();
field.init();
vector<int> unused;
for(int i=0; i<V; i++){
if(mapper[i].size() == 0){
unused.push_back(i);
}
for(auto pos : mapper[i]){
field[pos] = i;
}
}
if(unused.size() == 0) return;

vector<uint16_t> potential;

vector<vector<uint16_t>> nodes;
vector<MyBitset> adj;
for(int y=0; y<Vemb; y++)
for(int x=0; x<Vemb; x++){
int pos = get_pos(y,x);
if( field[pos] != -1 ) continue;
if( checked[pos] ) continue;
vector<uint16_t> s;
adj.push_back( get_adj(pos, s) );
nodes.push_back( s );
potential.push_back( adj.back().size() );
}

int m = potential.size();
shuffle(unused);





for(int i : unused){
vector<unsigned int> p(m, 0);
unsigned int p_sum = 0;
for(int j=0; j<m; j++){
int conn = (adj[j] & Mask[i]).size();
int n_conn = adj[j].size() - conn;
int sz = nodes[j].size();
if(sz == 0) continue;
p[j] = (conn*conn + n_conn) * 16 + sz + 10;
p_sum += p[j];
}
int r = x_rand(p_sum);
bool mapped = false;
for(int j=0; j<m; j++){
r -= p[j];
if( r<0 ){

int k = x_rand( nodes[j].size() );
swap(nodes[j][k], nodes[j].back());
int pos = nodes[j].back();
nodes[j].pop_back();
mapper[i].push_back(pos);
adj[j].set(i, true);
mapped = true;
break;
}
}
assert(mapped);
}

}
}
namespace Reconnect{
using namespace Util;
InitializedArray<3600, int16_t> field(-1);
InitializedArray<3600, int8_t> checked(0);
InitializedArray<500*500, int8_t> edgeUsed(0);
vector<MyBitset> Adj;



MyBitset get_adj(int start){
MyBitset adj(V);
static MyQueue<20000, uint16_t> q;
q.init();
int s = field[start];
q.push(start);
checked[start] = 1;
while(q.size()){
int pos = q.pop();
int y = get_y(pos);
int x = get_x(pos);
for(int k=0; k<8; k++){
int yy = y + dy[k];
int xx = x + dx[k];
if( out_of_bounds(yy,xx) ) continue;
int a_pos = get_pos(yy,xx);
int w = field[a_pos];
if( w == s ){
if( checked[a_pos] == 0 ){
checked[a_pos] = 1;
q.push(a_pos);
}
}else if(w >= 0){
adj.set(w, true);
}
}
}
return adj;
}
# 1953 "code_for_submission.cpp"
int make_connection(int u, int v, vector<vector<int>>& mapper){
static InitializedArray<3600, int16_t> distA(4095), distB(4095);
static InitializedArray<3600, int16_t> prevA(-1), prevB(-1);
static MyQueue<40000, int16_t> Qa, Qb;
distA.init();
distB.init();
prevA.init();
prevB.init();
Qa.init();
Qb.init();
for(int pos : mapper[u]){
distA[pos] = 0;
Qa.push(pos);
}
for(int pos : mapper[v]){
distB[pos] = 0;
Qb.push(pos);
}
int ca = -1, cb = -1;
int dd = 0;
for(dd=0; ca==-1 && cb==-1 && Qa.size() && Qb.size() && dd<=3 ; dd++){
while(Qa.size() && distA[Qa.peek()] == dd && ca==-1){
int pos = Qa.pop();
int y = get_y(pos);
int x = get_x(pos);
for(int k=0; k<8; k++){
int yy = y + dyx[k];
int xx = x + dxx[k];


if(out_of_bounds(yy,xx)) continue;
int a_pos = get_pos(yy,xx);
int w = field[a_pos];
if( distB[a_pos] <= dd+1 ){
ca = pos;
cb = a_pos;
break;
}
if( w == -1 ){
if( distA[a_pos] > dd+1 ){
distA[a_pos] = dd+1;
prevA[a_pos] = pos;
Qa.push( a_pos );
}
}
}
}
while(Qb.size() && distB[Qb.peek()] == dd && cb==-1){
int pos = Qb.pop();
int y = get_y(pos);
int x = get_x(pos);
for(int k=0; k<8; k++){
int yy = y + dyx[k];
int xx = x + dxx[k];


if(out_of_bounds(yy,xx)) continue;
int a_pos = get_pos(yy,xx);
int w = field[a_pos];
if( distA[a_pos] <= dd+1 ){
cb = pos;
ca = a_pos;
break;
}
if( w == -1 ){
if( distB[a_pos] > dd+1 ){
distB[a_pos] = dd+1;
prevB[a_pos] = pos;
Qb.push( a_pos );
}
}
}
}

}
if(ca == -1 || cb == -1){

return 0;
}
while(field[ca] == -1){
field[ca] = u;
mapper[u].push_back(ca);

int y = get_y(ca);
int x = get_x(ca);
for(int k=0; k<8; k++){
int yy = y + dy[k];
int xx = x + dx[k];
if(out_of_bounds(yy,xx)) continue;
int a_pos = get_pos(yy,xx);
int w = field[a_pos];
if( w < 0 || w == u ) continue;
Adj[u].set(w, true);
Adj[w].set(u, true);
}
ca = prevA[ca];
}
while(field[cb] == -1){
field[cb] = u;
mapper[v].push_back(cb);

int y = get_y(cb);
int x = get_x(cb);
for(int k=0; k<8; k++){
int yy = y + dy[k];
int xx = x + dx[k];
if(out_of_bounds(yy,xx)) continue;
int a_pos = get_pos(yy,xx);
int w = field[a_pos];
if( w < 0 || w == v ) continue;
Adj[v].set(w, true);
Adj[w].set(v, true);
}
cb = prevB[cb];
}
return 1;
}





void connect(vector<vector<int>>& mapper, bool connectInvalidEdge = true){

static FastPriorityQueue_2Layer<int> pq;
Adj = vector<MyBitset>(V, MyBitset(V));
field.init();
checked.init();
edgeUsed.init();

for(int i=0; i<V; i++){
for(int pos : mapper[i]){
field[pos] = i;
}
}

vector<int> reserevedCell;
for(int i=0; i<Vemb*Vemb; i++){
if( field[i] != -1 ) continue;
if( (x_rand()&1023) < 300 ){

field[i] = -2;
}
}
pq.clear();
for(int i=0; i<V; i++){
assert(mapper[i].size());
Adj[i] = get_adj( mapper[i].front() );
int potential = E[i].size() - (Adj[i]&Mask[i]).size();
assert( 500-potential >= 0 );
pq.push( (500-potential) >> (x_rand(3)), i );
}


int connCount = 0;
for(int t=0; t<V; t++){
int i = pq.pop().second;
if( x_rand(1024) < 100 ) continue;
shuffle(E[i]);
for(int j : E[i]){
if( Adj[i].get(j) ) continue;
if( edgeUsed[i*V+j] ) continue;
edgeUsed[i*V + j] = 1;
edgeUsed[j*V + i] = 1;
connCount += make_connection(i,j, mapper);
}
}
vis.push(mapper);




if(connectInvalidEdge == false) return;



pq.clear();
for(int i=0; i<V; i++){
int potential = V-1 - Adj[i].size();
pq.push( potential >> x_rand(3) , i );
}
connCount = 0;
for(int t=0; t<V; t++){
if( x_rand(1024) < 100 ) continue;
int i = pq.pop().second;
for(int j=0; j<V; j++){
if( i==j ) continue;
if( Adj[i].get(j) ) continue;
if( edgeUsed[i*V+j] ) continue;
edgeUsed[i*V + j] = 1;
edgeUsed[j*V + i] = 1;
connCount += make_connection(i,j, mapper);
}
}


}
}
namespace Fill{
using namespace Util;
InitializedArray<3600, int16_t> field(-1);
InitializedArray<3600, char> checked(0);
MyList<3600> frontier;

void set_frontier(int start){
MyBitset adj(V);
static MyQueue<20000, uint16_t> q;
q.init();
int s = field[start];
q.push(start);
checked[start] = 1;
while(q.size()){
int pos = q.pop();
int y = get_y(pos);
int x = get_x(pos);
for(int k=0; k<8; k++){
int yy = y + dy[k];
int xx = x + dx[k];
if( out_of_bounds(yy,xx) ) continue;
int a_pos = get_pos(yy,xx);
int w = field[a_pos];
if( w == s ){
if( checked[a_pos] == 0 ){
checked[a_pos] = 1;
q.push(a_pos);
}
}
if( w==-1 ){
frontier.insert( a_pos );
}
}
}
}

void put(vector<vector<int>>& mapper, int pos){
int y = get_y(pos);
int x = get_x(pos);
bool has_put = false;
int r = x_rand(8);
for(int k=0; k<8; k++){
int yy = y + dyx[(k+r)%8];
int xx = x + dxx[(k+r)%8];
if( out_of_bounds(yy,xx) ) continue;
int a_pos = get_pos(yy,xx);
int w = field[a_pos];
if( w == -1 ){
frontier.insert( a_pos );
}else if(!has_put){
has_put = true;
mapper[w].push_back(pos);
field[pos] = w;
}
}
}
void fill(vector<vector<int>>& mapper){
field.init();
checked.init();
frontier.clear();
for(int i=0; i<V; i++){
for(int pos : mapper[i]){
field[pos] = i;
}
}
for(int i=0; i<V; i++){
if( mapper[i].size() == 0 ) continue;
set_frontier(mapper[i].front());
}
int cnt = 0;
while( frontier.size() ){
cnt++;
int pos = frontier.random_pick();
frontier.erase(pos);
put(mapper, pos);
}
}
}
# 2291 "code_for_submission.cpp"
InitializedArray<640*640, int> cache(-114514893);
class StateEmp{
public:
vector<int16_t> field;
vector<MyBitset> connected;
vector<vector<int>> mapper;
vector<MyList<640>> adj;

int mapper_size[640];
int M;
vector<MyBitset> Mask;



vector<uint16_t> validConnection;

int numValidEdge;

int numUsedVertex;
int score;
int calc_score(){
int res = 5000;
res += 100 * numValidEdge;
res -= numUsedVertex - TestCase::V;





return res;
}





int swap(int u, int v){
using namespace Util;
cache.init();
assert(u<V || v<V);
static int a[2][640];

vector<int> cnt = {adj[u].size(), adj[v].size()};
for(int k=0; k<2; k++){
int z = k==0?u:v;



for(int i=0; i<cnt[k]; i++){
a[k][i] = adj[z].P[i];



}
}
# 2359 "code_for_submission.cpp"
for(int k=0; k<2; k++){
int z = k==0 ? u : v;
for(int i=0; i<cnt[k]; i++){
int w = a[k][i];

if( adj[z].has_key(w) == false ){
assert( (z==u && w==v) || (z==v && w==u) );
continue;
}
if( Mask[z].get(w) ){
numValidEdge--;
validConnection[z]--;
validConnection[w]--;
}
adj[z].erase(w);
adj[w].erase(z);
connected[z].set(w, false);
connected[w].set(z, false);
}
}
if( (u<V?1:0) ^ (v<V?1:0) ){


numUsedVertex -= (u<V ? mapper_size[u] : mapper_size[v]);
numUsedVertex += (u<V ? mapper_size[v] : mapper_size[u]);
}

for(int k=0; k<2; k++){
int z = k==0 ? v : u;
for(int i=0; i<cnt[k]; i++){
int w = a[k][i];

if( z == w ) w = (z^u^v);
if( adj[z].has_key(w) == true ){
assert( (z==u && w==v) || (z==v && w==u) );
continue;
}
if( Mask[z].get(w) ){
numValidEdge++;
validConnection[z]++;
validConnection[w]++;
}
adj[z].insert(w);
adj[w].insert(z);
connected[z].set(w, true);
connected[w].set(z, true);
}
}
# 2422 "code_for_submission.cpp"
std::swap(mapper_size[u], mapper_size[v]);
score = calc_score();
return score;
}



int get_swap_score_diff(int u, int v){
using namespace Util;

if(cache[u*640 + v] != -114514893){
return cache[u*640 + v];
}
assert(u<V || v<V);
int s = 0;
int e = 0;


e -= validConnection[u];
e -= validConnection[v];
e += (connected[v]&Mask[u]).size();
e += (connected[u]&Mask[v]).size();
if( adj[u].has_key(v) && Mask[u].get(v) ){
e += 2;
}
if( (u<V?1:0) ^ (v<V?1:0) ){
s += (u<V ? mapper_size[u] : mapper_size[v]);
s -= (u<V ? mapper_size[v] : mapper_size[u]);
}
s = s + e*100;
cache[u*640 + v] = s;
return s;
}





int init(vector<vector<int>>& mapper_){
using namespace Util;
M = mapper_.size();
field = vector<int16_t>(Vemb * Vemb, -1);
connected = vector<MyBitset>(M, MyBitset(M));

mapper = mapper_;
adj = vector<MyList<640>>(M);
for(int i=0; i<M; i++){
adj[i].clear();
}
validConnection = vector<uint16_t>(M, 0);
numValidEdge = 0;
numUsedVertex = 0;
Mask = vector<MyBitset>(M, MyBitset(M));
for(int i=0; i<V; i++){
for(auto j : E[i]){
Mask[i].set(j, true);
}
}
for(int i=0; i<M; i++){
mapper_size[i] = mapper[i].size();
assert( mapper[i].size() > 0 );
for(auto pos : mapper[i]){
field[pos] = i;
if( i<V ){
numUsedVertex++;
}
}
}
for(int i=0; i<M; i++){
for(auto pos : mapper[i]){
int y = get_y(pos);
int x = get_x(pos);
for(int k=0; k<8; k++){
int yy = y + dy[k];
int xx = x + dx[k];
if( out_of_bounds(yy,xx) ) continue;
int a_pos = get_pos(yy,xx);
int w = field[a_pos];
if( w == -1 || w == i ) continue;
connected[i].set(w, true);
connected[w].set(i, true);
adj[i].insert(w);
adj[w].insert(i);
}
}
}
for(int i=0; i<V; i++){
auto tmp = (connected[i] & Mask[i]).size();
numValidEdge += tmp;
validConnection[i] = tmp;
}
assert(numValidEdge % 2 == 0);
numValidEdge /= 2;

cache.init();
score = calc_score();
return score;
}



};
namespace EmptySet{
using namespace Util;
InitializedArray<3600, int16_t> field(-1);
int M;
InitializedArray<640, int> v_dist(1000000);
InitializedArray<3600, int> dist(1000000);
InitializedArray<3600, int> from(-1);
MyQueue<40000, int> q;

vector< pair<int,int> > bfs(int start){


if( start != -1 ){
q.init();
q.push( start );
dist[start] = 0;
from[start] = -1;
}
vector< pair<int,int> > res;

while( q.size() ){
int pos = q.pop();
int y = get_y(pos);
int x = get_x(pos);
int nx_d = dist[pos]+1;

for(int k=0; k<8; k++){
int yy = y + dyx[k];
int xx = x + dxx[k];
if( out_of_bounds(yy,xx) ) continue;
int a_pos = get_pos(yy,xx);
if( field[a_pos] == -1 ){
if( dist[a_pos] > nx_d ){
dist[a_pos] = nx_d;
from[a_pos] = pos;
q.push(a_pos);
}
}else{
int w = field[a_pos];
if( v_dist[w] > nx_d ){
v_dist[w] = nx_d;
dist[a_pos] = nx_d;
from[a_pos] = pos;
res.push_back( {dist[a_pos], a_pos} );
}
}
}
}
return res;
}

void connect(int v, int pos, vector<int>& m, MyBitset& adj){
q.init();
while( field[pos] == -1 ){
field[pos] = v;
dist[pos] = 0;
m.push_back(pos);
q.push( pos );
int y = get_y(pos);
int x = get_x(pos);
for(int k=0; k<8; k++){
int yy = y + dyx[k];
int xx = x + dxx[k];
if( out_of_bounds(yy,xx) ) continue;
int a_pos = get_pos(yy,xx);
int w = field[a_pos];
if( w != -1 && w != v ){
adj.set(w, true);
v_dist[w] = -1;
}
}
pos = from[pos];
}
assert( field[pos] == v );
}
bool is_connected(vector<int>& m){
set<int> used;
int start = m.front();
queue<int> q;
q.push(start);
used.insert(start);
while(q.size()){
int pos = q.front(); q.pop();
int y = get_y(pos);
int x = get_x(pos);
for(int k=0; k<8; k++){
int yy = y + dyx[k];
int xx = x + dxx[k];
if( out_of_bounds(yy,xx) ) continue;
int a_pos = get_pos(yy,xx);
if( field[a_pos] == field[start] ){
if( used.count(a_pos) == 0 ){
q.push(a_pos);
used.insert(a_pos);
}
}
}
}
assert( used.size() == m.size() );
return used.size() == m.size();
}

vector<vector<int>> set(vector<vector<int>> mapper){
field.init();
for(int i=0; i<V; i++){
assert( mapper[i].size() > 0 );
for(auto pos : mapper[i]){
field[pos] = i;
}
}
static MyList<3600> empty_cell;
empty_cell.clear();
for(int y=0; y<Vemb; y++)
for(int x=0; x<Vemb; x++){
int pos = get_pos(y,x);
if( field[pos] != -1 ) continue;
empty_cell.insert(pos);
}
M = mapper.size();


while( mapper.size() < 640 && empty_cell.size() > 0 && M-V < 30){
int pos = empty_cell.random_pick();
empty_cell.erase(pos);
if( field[pos] != -1 ) continue;
mapper.push_back( {pos} );
M = mapper.size();
v_dist.init();
dist.init();
from.init();
int u = M-1;
field[pos] = u;
v_dist[u] = -1;
MyBitset adj(M);
int y = get_y(pos);
int x = get_x(pos);
for(int k=0; k<8; k++){
int yy = y + dyx[k];
int xx = x + dxx[k];
if( out_of_bounds(yy,xx) ) continue;
int a_pos = get_pos(yy,xx);
if( field[a_pos] != -1 && field[a_pos] != u ){
adj.set(field[a_pos], true);
v_dist[field[a_pos]] = -1;
}
}

auto p = bfs(pos);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq(p.begin(), p.end());
while(pq.size()){
auto r = pq.top(); pq.pop();
int a_pos = r.second;
int w = field[a_pos];
assert(w != -1 && w != u);
int dd = r.first;
if( v_dist[ w ] == -1 ) continue;
v_dist[w] = -1;
connect( u, from[a_pos], mapper[u], adj );
p = bfs(-1);
for(auto z : p){
pq.push( z );
}
}
}
return mapper;
}
}
namespace SA_Emp{
using namespace Util;
bool accept(int diff, int t){
if(diff >= 0) return true;

double T = max( 1.6, - t * 10e-8 + 3.5 );
double w = diff ;

constexpr double a = 0.090;
if( -w*a > 31.5 * T ) return false;
long long k = 31.5 + (w*a/T);
long long x = 1ull << k;
return x_rand.pp() < x;


}
vector<vector<int>> last_mapper;





pair<int, vector<vector<int>>> SA(vector<vector<int>> mapper_, int numItr = 1600000, int resetItr = -1){
mapper_ = EmptySet::set(mapper_);

int M = mapper_.size();
StateEmp s;
int best_score = s.init(mapper_);
vector<uint16_t> perm(M);
iota(perm.begin(), perm.end(), 0);
vector<uint16_t> best_perm = perm;
int forced_update = 0;
int unforced_update = 0;
int best_update = 0;
static int tt = 0;
if( resetItr != -1){
tt = resetItr;
}
for(int t=0; t<numItr; t++, tt++){
if( (t&0x3FFFF) == 0){
if( my_time::getTime() > UCHIKIRI_TIME ){
break;
}
}
int prev_score = s.score;
int u;

u = x_rand(V);



int v;
if( (x_rand()&1023) < 1000){
v = E[u][ x_rand(E[u].size()) ];
if( tt>1000000 ){
if( s.adj[v].size() ){
int mx = -114514893;
int vv = v;
for(int i=0; i<3; i++){
int w = s.adj[v].random_pick();
if( w == u ) continue;
int d = s.get_swap_score_diff( u, w );
if( d > mx ){
mx = d;
vv = w;
}
}
v = vv;
}
}else{
if( s.adj[v].size() ){
v = s.adj[v].random_pick();
}
}
if( s.adj[u].has_key(v) && (x_rand()&1023) < 500 ){



v = x_rand(M);

}
}else{



v = x_rand(M);

}
if(u == v) continue;



int diff = s.get_swap_score_diff(u,v);





int next_score = diff + prev_score;
if( accept(diff, tt) ){
int nx_s = s.swap(u,v);
swap( perm[u], perm[v] );
# 2805 "code_for_submission.cpp"
if( diff >= 0 ){
unforced_update++;
}else{
forced_update++;
}

if( next_score > best_score ){
best_update++;
best_score = next_score;
best_perm = perm;

}
}else{

}
}
vector<vector<int>> best_mapper(V);
for(int i=0; i<V; i++){
best_mapper[i] = mapper_[ best_perm[i] ];
}
last_mapper = vector<vector<int>>(V);
for(int i=0; i<V; i++){
last_mapper[i] = mapper_[ perm[i] ];
}
return {best_score, best_mapper};
}
}
# 2898 "code_for_submission.cpp"
namespace ReconnectBFS{
using namespace Util;
InitializedArray<3600, int16_t> field(-1);
InitializedArray<500*500, char> failed(0);
vector<vector<int>> mapper;
vector<MyBitset> adj;
MyList<3600> reserved_cell;
void make_connection();
void connect(vector<vector<int>>& mapper_){
field.init();
failed.init();
adj = vector<MyBitset>(V, MyBitset(V));
reserved_cell.clear();
swap(mapper_, mapper);
for(int i=0; i<V; i++){
for(int pos : mapper[i]){
field[pos] = i;
}
}
for(int i=0; i<V; i++){
for(int pos : mapper[i]){
int y = get_y(pos);
int x = get_x(pos);
for(int k=0; k<8; k++){
int yy = y + dy[k];
int xx = x + dx[k];
if( out_of_bounds(yy,xx) ) continue;
int a_pos = get_pos(yy,xx);
int w = field[a_pos];
if( w >= 0 && w != i ){
adj[i].set(w, true);
adj[w].set(i, true);
}
}
}
}
for(int i=0; i<Vemb*Vemb; i++){
if( field[i] == -1 ){
if( (x_rand()&2047) < 10 ){
reserved_cell.insert(i);
field[i] = -2;
}
}
}
make_connection();
swap(mapper_, mapper);
}
InitializedArray<640, int> v_dist(1000000);
InitializedArray<3600, int> dist(1000000);
InitializedArray<3600, int> from(-1);
MyQueue<40000, int> q;

vector< pair<int,int> > bfs(int start){


if( start != -1 ){
q.init();
v_dist.init();
dist.init();
from.init();
v_dist[start] = -1;
assert(mapper[start].size());
for(int pos : mapper[start]){
q.push(pos);
dist[pos] = 0;
from[pos] = -1;
}
}
vector< pair<int,int> > res;
if( q.size() == 0 ) return {};
int v = field[q.peek()];
assert( v >= 0 );
while( q.size() ){
int pos = q.pop();
int y = get_y(pos);
int x = get_x(pos);
int nx_d = dist[pos]+1;

for(int k=0; k<8; k++){
int yy = y + dy[k];
int xx = x + dx[k];
if( out_of_bounds(yy,xx) ) continue;
int a_pos = get_pos(yy,xx);
if( field[a_pos] == -1 ){
if( dist[a_pos] > nx_d ){
dist[a_pos] = nx_d;
from[a_pos] = pos;
q.push(a_pos);
}
}else if(field[a_pos] >= 0){
int w = field[a_pos];
if( v_dist[w] > nx_d && adj[v].get(w) == false){
v_dist[w] = nx_d;
dist[a_pos] = nx_d;
from[a_pos] = pos;
res.push_back( {dist[a_pos], a_pos} );
}
}
}
}
return res;
}



int connect(int v, int a_pos){
int u = field[a_pos];
int d = dist[a_pos];
assert( adj[v].get(u) == false );
int pos = from[a_pos];
int sep = d/2;
d--;
static int path[3600];
int i = 0;
q.init();
while( field[pos] == -1 ){
path[i++] = pos;
int& f_pos = from[pos];
if( field[f_pos] >= 0 && field[f_pos] != v ){
int y = get_y(pos);
int x = get_x(pos);
for(int k=0; k<8; k++){
int yy = y + dy[k];
int xx = x + dx[k];
if( out_of_bounds(yy,xx) ) continue;
int b_pos = get_pos(yy,xx);
int w = field[b_pos];
if( w == -1 && dist[b_pos] < dist[pos] ){
from[pos] = b_pos;
break;
}
}
}
pos = from[pos];
}
if( pos < 0 || field[pos] != v ){


return 0;
}
for(int j=0; j<i; j++){
int z = j<sep ? u : v;
pos = path[j];
assert( field[pos] == -1 );
field[pos] = z;
dist[pos] = 0;
mapper[z].push_back(pos);
if( z == v ){
q.push( pos );
}
int y = get_y(pos);
int x = get_x(pos);
for(int k=0; k<8; k++){
int yy = y + dy[k];
int xx = x + dx[k];
if( out_of_bounds(yy,xx) ) continue;
int a_pos = get_pos(yy,xx);
int w = field[a_pos];
if( w >= 0 && w != z ){
adj[z].set(w, true);
adj[w].set(z, true);
v_dist[w] = -1;
}
}
}
return 1;
}
void make_connection(){
MyList<500> vertex;
for(int i=0; i<V; i++){
vertex.insert(i);
}
int connect_cnt = 0;
while(vertex.size()){
int v = vertex.random_pick();
vertex.erase(v);
v_dist.init();
dist.init();
from.init();

auto p = bfs(v);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq(p.begin(), p.end());
while(pq.size()){
auto r = pq.top(); pq.pop();
int a_pos = r.second;
int w = field[a_pos];
assert(w != -1 && w != v);
if( adj[v].get(w) ) continue;
if( v_dist[ w ] == -1 ) continue;

if( Mask[v].get(w) == false ) continue;

if(r.first > 9) break;
int dd = r.first;
v_dist[w] = -1;
connect_cnt += connect( v, a_pos );
p = bfs(-1);
for(auto z : p){
pq.push( z );
}
}
}

for(auto p : reserved_cell){
field[p] = -1;
}
for(int i=0; i<V; i++){
vertex.insert(i);
}
connect_cnt = 0;
while(vertex.size()){
int v = vertex.random_pick();
vertex.erase(v);
v_dist.init();
dist.init();
from.init();

auto p = bfs(v);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq(p.begin(), p.end());
while(pq.size()){
auto r = pq.top(); pq.pop();
int a_pos = r.second;
int w = field[a_pos];
assert(w != -1 && w != v);
if( adj[v].get(w) ) continue;
if( v_dist[ w ] == -1 ) continue;


int dd = r.first;
v_dist[w] = -1;
connect_cnt += connect( v, a_pos );
p = bfs(-1);
for(auto z : p){
pq.push( z );
}
}
}

}
}
vector<vector<int>> empSolver(){
vector<vector<int>> mapper;
int score = 0;
int run_count = 0;
while( my_time::getTime() < 1000 ){
run_count++;
auto tmp = RandomSolver::solve();
if( tmp.first > score ){
score = tmp.first;
mapper = tmp.second;
vis.push(mapper);
}
}



ReconnectBFS::connect(mapper);
vis.push(mapper);
score = Util::calcScore(mapper);
int best_score = score;
vector<vector<int>> best_mapper = mapper;
int loop_cnt = 0;
while( my_time::getTime() < UCHIKIRI_TIME ){
loop_cnt++;

auto r = SA_Emp::SA(mapper, 280000);
score = r.first;
mapper = r.second;
vis.push(mapper);
for(int t=0; t<15; t++){
mapper = Remover::remove(mapper);
}
vis.push(mapper);
Remapper::remap(mapper);
vis.push(mapper);
score = Util::calcScore(mapper);
if( best_score < score ){
best_score = score;
best_mapper = mapper;
}

mapper = SA_Emp::last_mapper;

for(int t=0; t<15; t++){
mapper = Remover::remove(mapper);
}
vis.push(mapper);
Remapper::remap(mapper);
vis.push(mapper);

ReconnectBFS::connect(mapper);

vis.push(mapper);

}
for(int t=0; t<30; t++){
mapper = Remover::remove(mapper);
}
vis.push(mapper);
Remapper::remap(mapper);
vis.push(mapper);
score = Util::calcScore(mapper);
if( best_score < score ){
best_score = score;
best_mapper = mapper;
}
vis.push(best_mapper);
return best_mapper;
}

int main(){
my_time::init();
TestCase::input();

Util::set_pxpy();


auto res = empSolver();
Util::output(res);
return 0;
}

Submission Info

Compile Error

code_for_submission.cpp: In function ‘void Util::output(std::vector<std::vector<int> >&)’:
code_for_submission.cpp:650:27: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘std::vector<int>::size_type {aka long unsigned int}’ [-Wformat=]
code_for_submission.cpp: In function ‘void TestCase::input()’:
code_for_submission.cpp:410:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
code_for_submission.cpp:417:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
code_for_submission.cpp:426:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result