| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1031883 |
2024-07-23T08:24:24 Z |
vjudge1 |
Mars (APIO22_mars) |
C++17 |
|
0 ms |
332 KB |
#include "mars.h"
#include<bits/stdc++.h>
using namespace std;
bitset<50> grid[50];
void flod(int i,int j){
if(i<0||i>30||j<0||j>30)return;
if(!grid[i][j]) return;
grid[i][j]=0;
flod(i-1,j);
flod(i+1,j);
flod(i,j+1);
flod(i,j-1);
}
string howmanyislands(int n){
for(int i=0;i<n;i++)
assert(grid[i].count()==n);
int ans=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
ans+=grid[i][j],flod(i,j);
string str;
for(int i=0;i<100;i++)
str+=48+(ans&1),ans>>=1;
return str;
}
string encode_grid(int i,int j){
string str;
for(int I=0;I<10;I++)
for(int J=0;J<10;J++)
str+=48+grid[i+I][j+J];
return str;
}
void putintogrid(string a,int i,int j){
int CC=0;
for(int I=0;I<10;I++) for(int J=0;J<10;J++)
grid[i+I][j+J]=grid[i+I][j+J]|a[CC++]=='1';
}
std::string process(std::vector <std::vector<std::string>> a, int i, int j, int k, int n) {
for(int i=0;i<2*n+1;i++)
grid[i].reset();
if(n<=4) {
for(int i=0;i<2*n+1;i++)
grid[i].reset();
if(i&1||j&1) return a[0][0];
if(max(i,j)==2*n-2*k-2) {
grid[i][j]=a[0][0][0]=='1';
grid[i+1][j]=a[1][0][0]=='1';
grid[i][j+1]=a[0][1][0]=='1';
grid[i+1][j+1]=a[1][1][0]=='1';
grid[i+2][j+1]=a[2][1][0]=='1';
grid[i+1][j+2]=a[1][2][0]=='1';
putintogrid(a[2][0],i+2,j);
putintogrid(a[2][2],i+2,j+2);
putintogrid(a[0][2],i,j+2);
} else return a[0][0];
if(k==n-1)
return howmanyislands(2*n+1);
return encode_grid(i,j);
}
int szofg=2*n;
set<int> important;
important.insert(0);
important.insert(szofg);
important.insert(szofg-10);
set<int>important2;
important2.insert(0);
important2.insert(szofg-10);
if(szofg>20)
important2.insert(szofg-20);
if(szofg>20)
important.insert(szofg-20);
if(k==n-1){
int k=2*n-9;
if(n==5) {
grid[i][j]=a[0][0][0]=='1';
grid[i+1][j]=a[1][0][0]=='1';
grid[i][j+1]=a[0][1][0]=='1';
grid[i+1][j+1]=a[1][1][0]=='1';
grid[i+2][j+1]=a[2][1][0]=='1';
grid[i+1][j+2]=a[1][2][0]=='1';
putintogrid(a[2][0],i+2,j);
putintogrid(a[2][2],i+2,j+2);
putintogrid(a[0][2],i,j+2);
}else
if(important2.size()==3)
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
putintogrid(a[i][j],max(0,szofg-7-(3-i)*10),max(0,szofg-7+(3-i)*10));
else {
putintogrid(a[0][0],0,0),putintogrid(a[2][2],k,k),putintogrid(a[2][0],k,0),putintogrid(a[0][2],0,k);
}
return howmanyislands(2*n+1);
}
if(k<5) {
for(int i=0;i<2*n+1;i++)
grid[i].reset();
if(i&1||j&1) return a[0][0];
int A=*--important.upper_bound(i);
int B=*--important.upper_bound(j);
if(max(i-A,j-B)==10-2*k-2||(!A&&!B&&max(i,j)==*++important.begin()-2-2*k)) {
grid[i][j]=a[0][0][0]=='1';
grid[i+1][j]=a[1][0][0]=='1';
grid[i][j+1]=a[0][1][0]=='1';
grid[i+1][j+1]=a[1][1][0]=='1';
grid[i+2][j+1]=a[2][1][0]=='1';
grid[i+1][j+2]=a[1][2][0]=='1';
putintogrid(a[2][0],i+2,j);
putintogrid(a[2][2],i+2,j+2);
putintogrid(a[0][2],i,j+2);
} else return a[0][0];
return encode_grid(i+!!i*(k==4),j+!!j*(k==4));
}
int transport[30][30][15];
for(auto i:important2){
for(auto j:important2){
int CC=5;
int origi=i;
int origj=j;
if(!i){
while(j)transport[0][j-=2][CC++]=1;
}else if(!j) {
while(i)transport[i-=2][0][CC++]=2;
}else if(i==j){
while(i)transport[i-=2][j-=2][CC++]=3;
} else if(i<j) {
while(i>2)transport[i-=2][j-=2][CC++]=3;
transport[--i][j-=2][CC++]=4;
while(j>2)transport[i-=2][j-=2][CC++]=1;
} else {
while(i>2)transport[i-=2][j-=2][CC++]=3;
transport[--i][j-=2][CC++]=5;
while(j>2)transport[i-=2][j-=2][CC++]=2;
}
i=origi;
j=origj;
}
}
if(i==0&&j==0)return a[0][0];
if(transport[i][j][k]){
if(transport[i][j][k]==1)
return a[0][2];
if(transport[i][j][k]==2)
return a[2][0];
if(transport[i][j][k]==3)
return a[2][2];
if(transport[i][j][k]==4)
return a[1][2];
if(transport[i][j][k]==5)
return a[2][1];
return a[0][0];
}
int x=max(i,j);
if(x==1&&important2.size()==3) {
int c=4+*++important2.begin()/2;
if(c==k){
return a[i][j];
}
}
return a[0][0];
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from mars.cpp:2:
mars.cpp: In function 'std::string howmanyislands(int)':
mars.cpp:16:31: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
16 | assert(grid[i].count()==n);
| ~~~~~~~~~~~~~~~^~~
mars.cpp: In function 'void putintogrid(std::string, int, int)':
mars.cpp:36:46: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
36 | grid[i+I][j+J]=grid[i+I][j+J]|a[CC++]=='1';
mars.cpp: In function 'std::string process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:132:41: warning: array subscript -1 is below array bounds of 'int [30][30][15]' [-Warray-bounds]
132 | while(j>2)transport[i-=2][j-=2][CC++]=2;
| ~~~~~~~~~~~~~~^
mars.cpp:113:9: note: while referencing 'transport'
113 | int transport[30][30][15];
| ^~~~~~~~~
mars.cpp:128:41: warning: array subscript -1 is below array bounds of 'int [30][30][15]' [-Warray-bounds]
128 | while(j>2)transport[i-=2][j-=2][CC++]=1;
| ~~~~~~~~~~~~~~^
mars.cpp:113:9: note: while referencing 'transport'
113 | int transport[30][30][15];
| ^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
