Submission #975472

#	Time	Username	Problem	Language	Result	Execution time	Memory
975472		oolimry	Mars (APIO22_mars)	C++17	100 / 100	1816 ms	7220 KiB

mars

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define showlist(x) cerr << #x << " is "; for(auto p : x) cerr << p << " "; cerr << endl;
typedef pair<int,int> ii;

/* 	credits: https://codeforces.com/blog/entry/103229?#comment-917407
* step 1: push all the information into a 5x5 square
* 	define a function group(i,j,k) that says at iteration k, cell i, j belongs to which group
* 	we want 25 groups at the end, group(i,j,k) is a function that roughly divides the grid into 25 roughly equal sized squares
* 
* step 2: divide the grid into 4 quadrants, each of size (n+1) by (n+1).
* 	for each quadrant, store the number of internal components, and the state of the border^ (row n and column n)
* 	store this at (0,0), (0,2), (2,0), (2,2) for each of the 4 quadrants respectively
* 
* step 3: on the 3x3 grid, 
*   decode the info at (0,0), (0,2), (2,0), (2,2)
* 	do more dfs on the row n and column n information to find the remaining components
* 	then add on the number on internal components in each quadrant
* 
* 
* ^ how to store the state of the border:
* 	we reserve 10 bits to store the number of internal components
* 	there are 2*n+1 <= 41 cells on the border --> 41 more bits
* 	the bits on the border, we divide them into consecutive groups
* 	observe the connectivity of the groups follows a bracket sequence
* 	for example, a b a c c a is (a_(b)_a_(c__c)a)
* 	store 1 bit for whether there is a open bracket before each group
* 	and 1 bit for whether there is a close bracket after
* 	max n+1 groups --> 2n+2 = 42 extra bits to store this info
*/

int grid[45][45];
int ccCounter = 1;
map<ii, vector<ii> > adj;
void resetgrid(){
	ccCounter = 1;
	adj.clear();
	for(int i = 0;i < 45;i++) for(int j = 0;j < 45;j++) grid[i][j] = 0;
}

void dfs(int i, int j){
	if(i < 0 or j < 0) return;
	if(grid[i][j] != -1) return;
	
	grid[i][j] = ccCounter;
	
	for(ii a : adj[ii(i,j)]) dfs(a.first, a.second);
	dfs(i+1,j);
	dfs(i-1,j);
	dfs(i,j+1);
	dfs(i,j-1);
}

void orTo(string &a, string b){ ///sets a = a | b
	for(int p = 0;p < 100;p++){
		if(b[p] == '1') a[p] = '1';
	}
}

int n, K;
ii group(int i, int j, int k){ ///step 1 --> group function
	vector<int> things = {};
	for(int i = 0;i <= 2*n - 2*k;i++) things.push_back((i*5) / (2*n - 2*k+1));
	sort(all(things));

	int G = things[i]*10 + things[j]; //((i) / sqsize) * 10 + (j) / sqsize;
	int P = ((i) % 10) * 10 + ((j)%10);
	return {G,P};
}

string writeNumber(int cnt){ ///writes a string with the first bits being the number
	string res = string(100,'0');
	for(int p = 0;p < 100;p++){
		if(cnt % 2 == 1) res[p] = '1';
		cnt /= 2;
	}
	return res;
}

/// we store the no. of internal components from 0-9
/// border cells 0 or 1 from 10-54
/// the bracket group info from 55 onwards
const int CNTBUFFER = 10; 
const int GROUPBUFFER = 55;

///used in step 3, used to decode the quadrant info from step 2
pair<int, vector<int> > decode(string res){ 
	int internalComponents = 0;
	
	for(int b = 0;b < CNTBUFFER;b++){
		if(res[b] == '1') internalComponents += (1LL <<b);
	}
	
	int b = CNTBUFFER;
	vector<int> colors;
	
	for(int i = 0;i <= 2*n;i++){
		colors.push_back(res[b] - '0');
		b++;
	}
	
	vector<vector<int> > groups;
	
	int pre = -1;
	for(int i = 0;i <= 2*n;i++){
		if(colors[i] == 1 ){
			if(pre != 1) groups.push_back({});
			groups.back().push_back(i);
		}
		
		pre = colors[i];
	}
	
	vector<int> S; 
	b = GROUPBUFFER;
	int cnt = 1;
	
	for(auto &v : groups){
		if(res[b] == '1') S.push_back(cnt++);
		b++;
		
		for(int i : v) colors[i] = S.back();
		
		if(res[b] == '1') S.pop_back();
		b++;
	}
	
	
	return {internalComponents, colors};
}


/// step 2 function, given the quadrant, return a string encoding
/// no. of internal components & border info
/// takes in a list of cells, rotated such that the border we're interested at top left corner
string generateCorner(vector<vector<int> > g){ 
	int internalComponents = 0;
	
	resetgrid();
	
	for(int i = 0;i <= n;i++){
		for(int j = 0;j <= n;j++){
			grid[i][j] = -g[i][j];
		}
	}
	
	for(int i = 0;i <= n;i++){
		for(int j = 0;j <= n;j++){
			if(grid[i][j] == -1){
				dfs(i,j);
				ccCounter++;
			}
		}
	}
	
	/// debug: coloring (color = component color) of the grid
	/* 
	for(int i = 0;i <= n;i++){
		for(int j = 0;j <= n;j++){
			cerr << grid[i][j] << " ";
		}
		cerr << endl;
	}
	
	//*/
	
	set<int> borderComponents;
	for(int i = 0;i <= n;i++){
		for(int j = 0;j <= n;j++){
			if((i == 0 or j == 0) and grid[i][j] != 0){
				borderComponents.insert(grid[i][j]);
			}
		}
	}
	
	internalComponents = ccCounter - 1 - sz(borderComponents);
	string res = writeNumber(internalComponents);
	
	vector<ii> order;
	for(int i = n;i >= 1;i--) order.push_back(ii(i,0));
	for(int j = 0;j <= n;j++) order.push_back(ii(0,j));
	
	vector<int> colors;
	for(ii cell : order) colors.push_back(grid[cell.first][cell.second]);
		
	vector<int> groups;
	
	int b = CNTBUFFER;
	int pre = -1;
	for(int x : colors){
		if(x != 0){
			res[b] = '1';
			
			if(pre != x) groups.push_back(x);
		}
		b++;
		pre = x;
	}
	
	map<int,vector<int> > grouppos;
	for(int i = 0;i < sz(groups);i++){
		grouppos[groups[i]].push_back(i);
	}
	
	b = GROUPBUFFER;
	for(int i = 0;i < sz(groups);i++){
		int g  = groups[i];
		if(i == grouppos[g][0]) res[b] = '1';
		b++;
		if(i == grouppos[g].back()) res[b] = '1';
		b++;
	}
		
	auto decoded = decode(res); 
	
	/// debug: check decoded.first == internalComponents
	//show(internalComponents); show(decoded.first); 
	
	
	/// debug: check decoded.second ~= colors
	//showlist(colors); showlist(decoded.second);
	
	
	return res;
}

///returns the number of internal components in the quadrant (di,dj)
///and also fills in the grid + the adjacency list
int lastStepConnectivity(int di, int dj, string res){
	vector<ii> order;
	for(int i = n;i >= 1;i--) order.push_back(ii(i+n,n));
	for(int j = 0;j <= n;j++) order.push_back(ii(n,j+n));
		
	for(ii &v : order){
		if(di == 0) v.first = 2*n - v.first;
		if(dj == 0) v.second = 2*n - v.second;
	}
	
	auto ddd = decode(res);
	int internalComponents = ddd.first;
	vector<int> colors = ddd.second;
	
	map<int, ii> pre;
	for(int i = 0;i < sz(order);i++){
		ii cell = order[i];
		int c = colors[i];
		if(c != 0){
			grid[cell.first][cell.second] = -1;
		
			if(pre.find(c) != pre.end()){
				ii cell2 = pre[c];
				adj[cell].push_back(cell2);
				adj[cell2].push_back(cell);
			}
			pre[c] = cell;
		}
	}
	
	return internalComponents;
}


 
string process(vector <vector<string>> a, int I, int J, int K, int _n){
	n = _n;
	
	/// debug: checking if the grouping algo is good
	/*
	for(int k = 0;k < n;k++){
		for(int i = 0;i <= 2*n - 2*k;i++){
			for(int j = 0;j <= 2*n - 2*k;j++){
				int g = group(i,j,k).first;
				if(g < 10) cerr << " ";
				cerr << g << " ";
			}
			cerr << endl;
		}
		cerr << endl;
	}
	exit(0);
	//*/
	
	
	if(_n == 1){
		resetgrid();
		for(int i = 0;i <= 2;i++){
			for(int j = 0;j <= 2;j++){
				if(a[i][j][0] == '1') grid[i][j] = -1;
			}
		}
		
		int ans = 0;
		for(int i = 0;i <= 2;i++){
			for(int j = 0;j <= 2;j++){
				if(grid[i][j] == -1){
					dfs(i,j);
					ans++;
				}
			}
		}
		
		string res = writeNumber(ans);
		return res;
	}
	
	string res = string(100 ,'0');
	
	if(K == 0){ ///first run
		for(int io = 0;io <= 2;io++){
			for(int jo = 0;jo <= 2;jo++){
				if(a[io][jo][0] == '1'){
					a[io][jo] = string(100, '0');
					a[io][jo][group(io+I,jo+J,0).second] = '1';
				}
				else a[io][jo] = string(100, '0');
			}
		}
	}
	
	if(K == n-1){ ///last phase --> convert to binary 
		resetgrid();
		
		int ans = 0;
		ans += lastStepConnectivity(0,0,a[0][0]);
		ans += lastStepConnectivity(0,2,a[0][2]);
		ans += lastStepConnectivity(2,0,a[2][0]);
		ans += lastStepConnectivity(2,2,a[2][2]);
		
		/// debug: check if the row n and column n border is copied correctly
		/*
		for(int i = 0;i <= 2*n;i++){
			for(int j = 0;j <= 2*n;j++){
				cerr << grid[i][j] << " ";
			}
			cerr << endl;
		}
		//*/
		
		int laterComponents = 0;
		for(int i = 0;i <= 2*n;i++){
			for(int j = 0;j <= 2*n;j++){
				if(grid[i][j] == -1){
					dfs(i,j);
					laterComponents++;
				}
			}
		}
			
		res = writeNumber(ans + laterComponents);
		
		return res;
	}
	
	if(K <= n-2){
		for(int i = 0;i <= 2;i++){
			for(int j = 0;j <= 2;j++){
				if(group(I,J,K+1).first == group(i+I, j+J, K).first){
					orTo(res, a[i][j]);
				} 
			}
		}
	}
	if(K == n-2){
		if(I == 1 or J == 1) return res;
		
		map<ii, ii> GPtoCell;
		for(int i = 0;i <= 2*n;i++){
			for(int j = 0;j <= 2*n;j++){
				GPtoCell[group(i,j,0)] = ii(i,j);
			}
		}

		vector<vector<int> > g;
		
		resetgrid();
		for(int io = 0;io <= 2;io++){
			for(int jo = 0;jo <= 2;jo++){
				int groupno = group(io+I,jo+J,K).first;
				for(int p = 0;p < 100;p++){
					if(a[io][jo][p] == '1'){
						ii cell = GPtoCell[{groupno, p}];
						grid[cell.first][cell.second] = 1;
					}
				}
			}
		}
		
		/// debug: check if the quadrant cells are copied correctly
		/*
		for(int i = 0;i <= 2*n;i++){
			for(int j = 0;j <= 2*n;j++){
				cerr << grid[i][j] << " ";
			}
			cerr << endl;
		}
		//*/
		
		int di = (I-1), dj = (J-1);
		
		for(int i = n;i >= 0 and i <= 2*n;i += di){
			g.push_back({});
			for(int j = n;j >= 0 and j <= 2*n;j += dj){
				g.back().push_back(grid[i][j]);
			}
		}
		
		res = generateCorner(g);		
	}
	
	return res;
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 7 / 7
• Subtask 6: 8 / 8
• Subtask 7: 10 / 10
• Subtask 8: 24 / 24
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11