Submission #974977

#TimeUsernameProblemLanguageResultExecution timeMemory
974977oolimryMars (APIO22_mars)C++17
36 / 100
152 ms5548 KiB
#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; /// attempt 3 store number of connected components? /// push the values up to the LHS 3x3 square and then process the border information int grid[45][45]; int ccNumber[45][45]; map<ii, vector<ii> > adj; int CNTBUFFER = 14; ///bits used just to store the size int ccCounter = 0; void resetgrid(){ ccCounter = 1; adj.clear(); for(int i = 0;i < 45;i++) for(int j = 0;j < 45;j++) grid[i][j] = 0; for(int i = 0;i < 45;i++) for(int j = 0;j < 45;j++) ccNumber[i][j] = 0; } void dfs(int i, int j){ if(i < 0 or j < 0) return; if(grid[i][j] == 0) return; grid[i][j] = 0; ccNumber[i][j] = ccCounter; for(ii cell : adj[ii(i,j)]) dfs(cell.first,cell.second); dfs(i+1,j); dfs(i-1,j); dfs(i,j+1); dfs(i,j-1); } ///return the layer, and the position in that layer ii layer(int i, int j){ int L = max(i,j); int pos = abs(i - L) + abs(j - 0); return {L,pos}; } vector<ii> cellsOnLayer(int L){ vector<ii> cells; for(int j = 0;j <= L;j++) cells.push_back({L,j}); for(int i = L-1;i >= 0;i--) cells.push_back({i,L}); return cells; } 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; } void orTo(string &a, string b){ for(int p = 0;p < 100;p++){ if(b[p] == '1') a[p] = '1'; } } struct cornerInfo{ int internalComponents = 0; vector<int> border = {}; }; string cornerInfoToString(cornerInfo C){ string res = writeNumber(C.internalComponents); int b = CNTBUFFER; vector<int> S; set<int> instack; for(int x : C.border){ if(x == 0){ ///0 = zero res[b] = '0'; res[b+1] = '0'; b += 2; } else if(instack.find(x) == instack.end()){ ///01 = push //show2("01", x); res[b] = '0'; res[b+1] = '1'; b += 2; S.push_back(x); instack.insert(x); } else{ //show2("DOES THIS TRIGGER", x); while(S.back() != x){ ///10 = popback res[b] = '1'; res[b+1] = '0'; b += 2; instack.erase(S.back()); S.pop_back(); } res[b] = '1'; res[b+1] = '1'; b += 2; } } //show(res); return res; } cornerInfo stringToCornerInfo(string s, int szOfBorder){ cornerInfo C; for(int b = CNTBUFFER;b >= 0;b--){ C.internalComponents *= 2; if(s[b] == '1') C.internalComponents++; } int b = CNTBUFFER; vector<int> S; int cc = 1; while(sz(C.border) < szOfBorder){ //showlist(S); string command = "00"; command[0] = s[b]; command[1] = s[b+1]; //show(command); if(command == "00") C.border.push_back(0); if(command == "01"){ C.border.push_back(cc); S.push_back(cc); cc++; } if(command == "10") S.pop_back(); if(command == "11"){ C.border.push_back(S.back()); } b += 2; } return C; } string process(vector <vector<string>> a, int I, int J, int K, int n){ string res = string(100,'0'); /* testing cornerInfo conversion cornerInfo C; C.internalComponents = 4; C.border = {1,0,3,0,4}; string S = cornerInfoToString(C); show(S); C = stringToCornerInfo(S, 5); show(C.internalComponents); showlist(C.border); return res; */ //cerr << I << " " << J << " " << K << endl; if(K == 0){ ///first run for(int i = 0;i <= 2;i++){ for(int j = 0;j <= 2;j++){ if(a[i][j][0] == '1'){ a[i][j] = string(100, '0'); ii info = layer(I+i, j+J); a[i][j][info.second] = '1'; } else a[i][j] = string(100, '0'); } } if(I == 0 and J == 0){ cornerInfo C; C.internalComponents = 0; if(a[0][0][0] == '1') C.border = {1}; else C.border = {0}; a[0][0] = cornerInfoToString(C); } } if(I == 0 and J == 0){ /// do the terrible graph thing resetgrid(); int layer0 = K*2; int layer1 = layer0 + 1; int layer2 = layer1 + 1; auto layer0cells = cellsOnLayer(layer0); auto layer1cells = cellsOnLayer(layer1); auto layer2cells = cellsOnLayer(layer2); show(a[0][0]); cornerInfo C = stringToCornerInfo(a[0][0], sz(layer0cells)); showlist(C.border); string layer1String = string(100, '0'); string layer2String = string(100, '0'); for(int i = 0;i <= 2;i++){ for(int j = 0;j <= 2;j++){ if(i == 0 and j == 0) continue; if(i == 2 or j == 2) orTo(layer2String, a[i][j]); else orTo(layer1String, a[i][j]); } } map<int, ii> prevSameComponent; for(int a = 0;a < sz(layer0cells);a++){ ii cell = layer0cells[a]; int cc = C.border[a]; if(cc != 0) grid[cell.first][cell.second] = 1; if(cc != 0 and prevSameComponent.find(cc) != prevSameComponent.end()){ ii cell2 = prevSameComponent[cc]; adj[cell].push_back(cell2); adj[cell2].push_back(cell); } prevSameComponent[cc] = cell; } for(int a = 0;a < sz(layer1cells);a++){ ii cell = layer1cells[a]; if(layer1String[a] == '1') grid[cell.first][cell.second] = 1; else grid[cell.first][cell.second] = 0; } for(int a = 0;a < sz(layer2cells);a++){ ii cell = layer2cells[a]; if(layer2String[a] == '1') grid[cell.first][cell.second] = 1; else grid[cell.first][cell.second] = 0; } for(int i = 0;i <= 2*n;i++){ for(int j = 0;j <= 2*n;j++){ //cerr << grid[i][j] << " "; } //cerr << endl; } for(int i = 0;i <= 2*n;i++) for(int j = 0;j <= 2*n;j++){ if(grid[i][j] != 0){ dfs(i,j); ccCounter++; } } set<int> borderComponents; for(ii cell : layer2cells){ int cc = ccNumber[cell.first][cell.second]; if(cc != 0) borderComponents.insert(cc); } C.internalComponents += ccCounter - sz(borderComponents) - 1; /* bad for(int i = 0;i <= 2*n;i++) for(int j = 0;j <= 2*n;j++){ int cc = ccNumber[i][j]; if(cc != 0 and borderComponents.find(cc) == borderComponents.end()){ C.internalComponents++; } } */ map<int,int> disc; int discCnt = 1; for(int x : borderComponents) disc[x] = discCnt++; C.border.clear(); for(ii cell : layer2cells){ int cc = ccNumber[cell.first][cell.second]; if(cc == 0) C.border.push_back(0); else C.border.push_back(disc[cc]); } // show(C.internalComponents); showlist(C.border); if(K == n-1){ ///final run int ans = C.internalComponents + sz(borderComponents); res = writeNumber(ans); } else{ ///finally write the cell info res = cornerInfoToString(C); } } else{ for(int i = 0;i <= 2;i++){ for(int j = 0;j <= 2;j++){ if(layer(I,J).first == layer(i+I,j+J).first - 2) orTo(res, a[i][j]); } } } // cerr << res << endl; return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...