QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #355630 | #5101. Crystal Crosswind | InfinityNS# | WA | 1ms | 9920kb | C++14 | 4.1kb | 2024-03-17 00:14:43 | 2024-03-17 00:14:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define f first
#define s second
const int N=1e3+1,K=10;
int dx,dy,k;
bool taken[N][N];
pair<int,int> add(pair<int,int> a,pair<int,int> b){
return {a.f+b.f,a.s+b.s};
}
pair<int,int> sub(pair<int,int> a,pair<int,int> b){
return {a.f-b.f,a.s-b.s};
}
bool inside(pair<int,int> a){
return a.f>=0&&a.f<dx&&a.s>=0&&a.s<dy;
}
bool ink[N][N][K];
vector<pair<int,int>> dr(K);
bool blocked[N][N];
int cntCan[N][N];
bool added[N][N];
int main(){
scanf("%i %i %i",&dx,&dy,&k);
vector<vector<pair<int,int>>> a(k);
queue<pair<int,int>> q;
for(int i=0;i<k;i++){
scanf("%i %i",&dr[i].f,&dr[i].s);
int b;
scanf("%i",&b);
for(int j=0;j<b;j++){
int x,y;
scanf("%i %i",&x,&y);
x--;y--;
a[i].pb({x,y});
ink[x][y][i]=1;
if(!taken[x][y]){
taken[x][y]=1;
q.push({x,y});
}
}
}
while(q.size()){
pair<int,int> tr=q.front();
q.pop();
for(int i=0;i<k;i++){
if(ink[tr.f][tr.s][i])continue;
pair<int,int> a=sub(tr,dr[i]);
if(!taken[a.f][a.s]){
taken[a.f][a.s]=1;
q.push(a);
}
}
}
for(int i=0;i<dy;i++){
for(int j=0;j<dx;j++){
printf("%c",taken[j][i]?'#':'.');
}
printf("\n");
}
for(int i=0;i<k;i++){
for(auto p:a[i]){
pair<int,int> x=sub(p,dr[i]);
if(inside(x)){
blocked[x.f][x.s]=1;
}
}
}
for(int i=0;i<dx;i++){
for(int j=0;j<dy;j++){
if(taken[i][j]){
for(int o=0;o<k;o++){
pair<int,int> a=add({i,j},dr[o]);
if(inside(a)){
cntCan[a.f][a.s]++;
if(!blocked[a.f][a.s]&&!taken[a.f][a.s]){
q.push(a);
taken[a.f][a.s]=1;
added[a.f][a.s]=1;
}
}
}
}
}
}
while(q.size()){
pair<int,int> tr=q.front();
q.pop();
for(int o=0;o<k;o++){
pair<int,int> a=add(tr,dr[o]);
if(inside(a)){
cntCan[a.f][a.s]++;
if(!blocked[a.f][a.s]&&!taken[a.f][a.s]){
q.push(a);
taken[a.f][a.s]=1;
added[a.f][a.s]=1;
}
}
}
}
for(int i=0;i<dx;i++){
for(int j=0;j<dy;j++){
if(taken[i][j]){
if(added[i][j]&&cntCan[i][j]!=k){
added[i][j]=0;
q.push({i,j});
taken[i][j]=0;
for(int o=0;o<k;o++){
pair<int,int> a=add({i,j},dr[o]);
if(inside(a)){
cntCan[a.f][a.s]--;
if(added[a.f][a.s]&&cntCan[a.f][a.s]!=k){
q.push(a);
taken[a.f][a.s]=0;
added[a.f][a.s]=0;
}
}
}
}
}
}
}
while(q.size()){
pair<int,int> tr=q.front();
q.pop();
for(int o=0;o<k;o++){
pair<int,int> a=add(tr,dr[o]);
if(inside(a)){
cntCan[a.f][a.s]--;
if(added[a.f][a.s]&&cntCan[a.f][a.s]!=k){
q.push(a);
taken[a.f][a.s]=0;
added[a.f][a.s]=0;
}
}
}
}
printf("\n");
for(int i=0;i<dy;i++){
for(int j=0;j<dx;j++){
printf("%c",taken[j][i]?'#':'.');
}
printf("\n");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5784kb
input:
4 1 1 0 1 2 1 1 3 1
output:
#.#. #.#.
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 8116kb
input:
4 4 2 1 0 4 2 4 2 1 1 3 1 2 -1 0 4 4 3 4 2 3 1 3 4
output:
.##. #### #### .##. .##. #### #### .##.
result:
ok 9 lines
Test #3:
score: 0
Accepted
time: 1ms
memory: 7900kb
input:
8 12 1 -1 -4 10 5 7 2 4 1 5 5 11 1 6 5 3 8 11 5 1 1 4 7 3
output:
....#... ........ ....#.#. ##...... #....... #....... ....#... ........ ........ ........ ....#..# ........ ....#... ........ ..#####. ##...... #....... #....... ...##.#. ........ ........ ........ ....#..# ........
result:
ok 25 lines
Test #4:
score: 0
Accepted
time: 1ms
memory: 7844kb
input:
4 4 2 1 0 6 2 1 1 2 1 3 4 3 2 4 4 2 -1 0 6 4 2 2 2 2 3 3 1 3 4 4 3
output:
.##. ##.# ##.# .##. .##. ##.# ##.# .##.
result:
ok 9 lines
Test #5:
score: 0
Accepted
time: 1ms
memory: 8120kb
input:
8 10 1 -6 -6 25 7 3 8 5 8 6 4 5 4 4 3 2 5 3 6 8 5 4 1 9 1 8 7 10 8 4 2 7 3 9 2 4 3 10 4 6 2 10 3 6 8 8 6 10 4 3 6 1 7 9
output:
.....#.. ..#..... ...##.#. .#.##..# ...#...# ..##...# .#...... #....#.# #.#...#. .##..##. .....#.. .##..... #..##.#. ##.##..# ...#...# ..##...# .#...... #....#.# #.#...#. .##..##.
result:
ok 21 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 9920kb
input:
30 25 2 9 -15 229 27 8 13 20 25 20 15 9 7 16 23 4 2 18 20 21 21 24 19 24 2 23 19 18 25 7 11 6 7 5 4 12 15 25 13 1 28 20 9 1 8 8 17 21 3 1 21 20 14 20 1 12 14 16 9 5 19 17 7 24 11 20 15 18 15 11 28 12 9 15 19 20 30 15 4 17 10 13 4 9 20 24 2 24 13 9 20 25 25 24 11 14 20 19 24 12 9 9 3 5 27 14 19 12 12...
output:
..##...##..##....####.....##.. ..........###............#.... .......###.##.#.#.....##..##.# ...###.....#..#.....#.#...#.#. #.##..#.#.#...#.......#..#.#.. #.........#........##..#..#... ...#....#.#....#.##.....#..#.. .......##...##.#..#.#.#..##.#. ...#....#####.#.....##.###.... .#..##.......#...##.#...
result:
ok 51 lines
Test #7:
score: 0
Accepted
time: 0ms
memory: 8100kb
input:
20 20 3 -4 -3 53 18 20 2 10 7 5 17 18 14 6 14 8 13 19 9 18 17 16 20 15 3 20 7 2 8 7 17 6 1 19 20 7 7 6 13 1 18 16 19 14 8 8 19 20 8 20 7 18 2 9 1 4 16 20 2 17 19 19 15 13 20 12 18 10 20 19 8 12 17 13 17 10 18 18 12 19 9 19 20 3 20 4 1 20 20 6 8 5 19 18 17 17 20 16 16 7 19 17 18 14 2 1 19 6 18 8 -12 ...
output:
.#.....#...##....... ......#..#.......... ...#........#.#....# #..........#...#...# ......##.....#...... ......##.....#..#.## .....#.#.......#...# .......#.#...#...#.. .#.##......#........ .#.....#.#......##.. ......#.#.#..#...... .......##......#...# ...#......#####.#... .......#..#.#.#..##. ..#......
result:
ok 41 lines
Test #8:
score: 0
Accepted
time: 1ms
memory: 7976kb
input:
30 25 3 -20 0 192 26 25 24 20 5 5 22 25 24 25 5 10 27 25 21 8 20 24 20 4 14 17 12 19 17 19 5 19 3 14 16 4 22 23 18 11 21 23 27 7 11 6 3 8 25 4 29 21 28 12 18 21 27 21 23 16 26 13 25 9 15 2 23 24 28 6 26 21 22 21 17 23 19 17 30 12 24 12 26 16 24 5 21 2 25 12 30 24 18 25 30 14 30 7 26 24 25 21 29 17 2...
output:
.#.#...........##..#.##..#.##. ........#.....##...##....##.#. ..##.......#..#.......##.....# .#...#.........#...#.#..#...#. ...##....#...........#.#..###. ..........#..........#.....### ...#..#....#.#....##....#.##.# #.#.....#........#..#....#..#. ...##.......#..##....#..#..... ....#.....#......#......
result:
ok 51 lines
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 7928kb
input:
20 20 1 5 5 29 4 17 16 18 9 4 2 7 1 11 13 9 8 19 13 10 10 1 3 6 8 14 8 6 15 17 13 17 5 10 5 15 1 17 16 8 13 6 11 7 1 18 5 1 19 15 7 17 2 5 12 19 14 11 13 7 1 2
output:
....#....#.......... #................... .................... ........#........... .#.................. ..#....#....#....... .#........#.#....... ...............#.... ............#....... ....#.......#....... #............#...... .................... .................... .......#............ ....#....
result:
wrong answer 32nd lines differ - expected: '#......#....###..#.#', found: '#......#....##...#..'