Submission #975454

#	Time	Username	Problem	Language	Result	Execution time	Memory
975454		oolimry	Mars (APIO22_mars)	C++17	100 / 100	1891 ms	7768 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;
 
const int CNTBUFFER = 10;
const int GROUPBUFFER = 55;

///attempt 4: push into 5x5 and then see how from there
/// stuff for dfs
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){
	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){
	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 sqsize = (5 + 2*n - 2*k) / 5;
	//if(i == 2 and j == 2) show2(k, sqsize);
	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){
	string res = string(100,'0');
	for(int p = 0;p < 100;p++){
		if(cnt % 2 == 1) res[p] = '1';
		cnt /= 2;
	}
	return res;
}


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

string generateCorner(vector<vector<int> > g){
	/*
	for(auto v : g){
		for(int x : v) cerr << x << " ";
		cerr << endl;
	}
	cerr << endl;
	//*/
	
	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++;
			}
		}
	}
	//*
	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]);
	
	//showlist(colors);
	
	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;
	}
	
	//showlist(groups);
	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++;
	}
	
	
	
	
	show(res);
	
	//auto decoded = decode(res);
	
	show(internalComponents);
	//show(decoded.first);
	
	showlist(colors);
	//showlist(decoded.second);
	
	cerr << endl;
	return res;
}

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));
	
	//if(di == 0) reverse(all(order));
	
	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;
	
	//show2(sz(colors), sz(order));
	show2(di,dj);
	showlist(colors);
	
	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);
				
				show2(cell.first, cell.second);
				show2(cell2.first, cell2.second);
			}
			pre[c] = cell;
		}
	}
	
	return internalComponents;
}


 
string process(vector <vector<string>> a, int I, int J, int K, int _n){
	n = _n;
	//cerr << I << " " << J << " " << K << endl;				
	
	/*
	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]);
		
		//*
		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++;
				}
			}
		}
		
		show2(ans, 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;
					}
				}
			}
		}
		
		//*
		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]);
				//cerr << "(" << i << " " << j << ") ";
			}
			//cerr << endl;
		}
		
		res = generateCorner(g);		
	}
	
	//cerr << res << endl;
	
	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