| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 974922 |
2024-05-04T07:15:18 Z |
oolimry |
Mars (APIO22_mars) |
C++17 |
|
8 ms |
4340 KB |
#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 = 10; ///bits used just to store the size
int ccCounter = 0;
set<int> mergedComponents;
void resetgrid(){
ccCounter = 1;
mergedComponents.clear();
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] == 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;
for(int x : C.border){
if(x == 0) b++; ///write 0 there
else{
res[b] = '1'; b++; ///write 1 to mark it as 1
for(int bit = 0;bit < 5;bit++){
if(x % 2 == 1) res[b] = '1';
x /= 2;
b++;
}
}
}
return res;
}
cornerInfo stringToCornerInfo(string s, int szOfBorder){
cornerInfo C;
for(int b = 9;b >= 0;b--){
C.internalComponents *= 2;
if(s[b] == '1') C.internalComponents++;
}
int b = CNTBUFFER;
while(sz(C.border) < szOfBorder){
if(s[b] == '0'){
C.border.push_back(0);
b++;
}
else{
b++;
int cc = 0;
for(int bit = 0;bit < 5;bit++){
if(s[b] == '1') cc += (1<<bit);
b++;
}
C.border.push_back(cc);
}
}
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);
cornerInfo C = stringToCornerInfo(a[0][0], sz(layer0cells));
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);
show2(cell.first, cell.second);
show2(cell2.first, cell2.second);
}
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 time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
