Submission #1092213

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1092213	2024-09-23T15:02:00 Z	onlk97	Cell Automaton (JOI23_cell)	C++14	16 / 100	3377 ms	17748 KB

cell

#include <bits/stdc++.h>
using namespace std;
int n,q;
int x[100010],y[100010],t[500010];
bool small(){
    if (*min_element(x+1,x+n+1)<-1000||*max_element(y+1,y+n+1)>1000) return 0;
    if (*min_element(y+1,y+n+1)<-1000||*max_element(y+1,y+n+1)>1000) return 0;
    return t[q]<=1000;
}
const int X=4010;
bitset <X*X> b[5]; 
void gosmall(){
    b[0].reset(); b[1].reset(); b[2].reset();
    for (int i=1; i<=n; i++) b[0][X*(x[i]+X/2)+(y[i]+X/2)]=1;
    for (int i=0; i<X*X; i++) b[3][i]=1;
    int tme=0;
    for (int i=1; i<=q; i++){
        while (tme<t[i]){
            tme++;
            int ths=tme%3;
            int prv=(ths+2)%3,prv2=(ths+1)%3;
            b[ths].reset();
            b[4]=b[prv]; b[4]<<=X;
            b[ths]=b[4];
            b[4]=b[prv]; b[4]>>=X;
            b[ths]|=b[4];
            b[4]=b[prv]; b[4]<<=1;
            b[ths]|=b[4];
            b[4]=b[prv]; b[4]>>=1;
            b[ths]|=b[4];
            b[ths]&=(b[3]^b[prv])&(b[3]^b[prv2]);
        }
        cout<<b[tme%3].count()<<'\n';
    }
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>q;
    for (int i=1; i<=n; i++) cin>>x[i]>>y[i];
    for (int i=1; i<=q; i++) cin>>t[i];
    if (small()) gosmall();
}

Subtask #1

4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	161 ms	15964 KB	Output is correct
2	Correct	165 ms	16208 KB	Output is correct
3	Correct	155 ms	15964 KB	Output is correct
4	Correct	158 ms	15956 KB	Output is correct
5	Correct	157 ms	15952 KB	Output is correct
6	Correct	165 ms	15964 KB	Output is correct
7	Correct	163 ms	16184 KB	Output is correct
8	Correct	156 ms	16212 KB	Output is correct
9	Correct	166 ms	15952 KB	Output is correct
10	Correct	158 ms	16184 KB	Output is correct
11	Correct	158 ms	16188 KB	Output is correct
12	Correct	161 ms	15952 KB	Output is correct
13	Correct	157 ms	16200 KB	Output is correct
14	Correct	157 ms	16196 KB	Output is correct
15	Correct	158 ms	16196 KB	Output is correct
16	Correct	162 ms	15956 KB	Output is correct
17	Correct	156 ms	15960 KB	Output is correct
18	Correct	155 ms	15960 KB	Output is correct
19	Correct	157 ms	16344 KB	Output is correct
20	Correct	160 ms	15956 KB	Output is correct
21	Correct	155 ms	15952 KB	Output is correct
22	Correct	154 ms	16184 KB	Output is correct
23	Correct	157 ms	15960 KB	Output is correct
24	Correct	155 ms	15964 KB	Output is correct
25	Correct	160 ms	15956 KB	Output is correct
26	Correct	159 ms	16184 KB	Output is correct
27	Correct	165 ms	16184 KB	Output is correct
28	Correct	160 ms	15956 KB	Output is correct

Subtask #2

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	161 ms	15964 KB	Output is correct
2	Correct	165 ms	16208 KB	Output is correct
3	Correct	155 ms	15964 KB	Output is correct
4	Correct	158 ms	15956 KB	Output is correct
5	Correct	157 ms	15952 KB	Output is correct
6	Correct	165 ms	15964 KB	Output is correct
7	Correct	163 ms	16184 KB	Output is correct
8	Correct	156 ms	16212 KB	Output is correct
9	Correct	166 ms	15952 KB	Output is correct
10	Correct	158 ms	16184 KB	Output is correct
11	Correct	158 ms	16188 KB	Output is correct
12	Correct	161 ms	15952 KB	Output is correct
13	Correct	157 ms	16200 KB	Output is correct
14	Correct	157 ms	16196 KB	Output is correct
15	Correct	158 ms	16196 KB	Output is correct
16	Correct	162 ms	15956 KB	Output is correct
17	Correct	156 ms	15960 KB	Output is correct
18	Correct	155 ms	15960 KB	Output is correct
19	Correct	157 ms	16344 KB	Output is correct
20	Correct	160 ms	15956 KB	Output is correct
21	Correct	155 ms	15952 KB	Output is correct
22	Correct	154 ms	16184 KB	Output is correct
23	Correct	157 ms	15960 KB	Output is correct
24	Correct	155 ms	15964 KB	Output is correct
25	Correct	160 ms	15956 KB	Output is correct
26	Correct	159 ms	16184 KB	Output is correct
27	Correct	165 ms	16184 KB	Output is correct
28	Correct	160 ms	15956 KB	Output is correct
29	Correct	2776 ms	16188 KB	Output is correct
30	Correct	2745 ms	15952 KB	Output is correct
31	Correct	2756 ms	16212 KB	Output is correct
32	Correct	2771 ms	17748 KB	Output is correct
33	Correct	2776 ms	15964 KB	Output is correct
34	Correct	3377 ms	16172 KB	Output is correct
35	Correct	2762 ms	16212 KB	Output is correct
36	Correct	1426 ms	16184 KB	Output is correct
37	Correct	1384 ms	16192 KB	Output is correct
38	Correct	2728 ms	16208 KB	Output is correct
39	Correct	2717 ms	16288 KB	Output is correct
40	Correct	2712 ms	17744 KB	Output is correct

Subtask #3

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	15 ms	3160 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	15 ms	3160 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	344 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	344 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	161 ms	15964 KB	Output is correct
2	Correct	165 ms	16208 KB	Output is correct
3	Correct	155 ms	15964 KB	Output is correct
4	Correct	158 ms	15956 KB	Output is correct
5	Correct	157 ms	15952 KB	Output is correct
6	Correct	165 ms	15964 KB	Output is correct
7	Correct	163 ms	16184 KB	Output is correct
8	Correct	156 ms	16212 KB	Output is correct
9	Correct	166 ms	15952 KB	Output is correct
10	Correct	158 ms	16184 KB	Output is correct
11	Correct	158 ms	16188 KB	Output is correct
12	Correct	161 ms	15952 KB	Output is correct
13	Correct	157 ms	16200 KB	Output is correct
14	Correct	157 ms	16196 KB	Output is correct
15	Correct	158 ms	16196 KB	Output is correct
16	Correct	162 ms	15956 KB	Output is correct
17	Correct	156 ms	15960 KB	Output is correct
18	Correct	155 ms	15960 KB	Output is correct
19	Correct	157 ms	16344 KB	Output is correct
20	Correct	160 ms	15956 KB	Output is correct
21	Correct	155 ms	15952 KB	Output is correct
22	Correct	154 ms	16184 KB	Output is correct
23	Correct	157 ms	15960 KB	Output is correct
24	Correct	155 ms	15964 KB	Output is correct
25	Correct	160 ms	15956 KB	Output is correct
26	Correct	159 ms	16184 KB	Output is correct
27	Correct	165 ms	16184 KB	Output is correct
28	Correct	160 ms	15956 KB	Output is correct
29	Correct	2776 ms	16188 KB	Output is correct
30	Correct	2745 ms	15952 KB	Output is correct
31	Correct	2756 ms	16212 KB	Output is correct
32	Correct	2771 ms	17748 KB	Output is correct
33	Correct	2776 ms	15964 KB	Output is correct
34	Correct	3377 ms	16172 KB	Output is correct
35	Correct	2762 ms	16212 KB	Output is correct
36	Correct	1426 ms	16184 KB	Output is correct
37	Correct	1384 ms	16192 KB	Output is correct
38	Correct	2728 ms	16208 KB	Output is correct
39	Correct	2717 ms	16288 KB	Output is correct
40	Correct	2712 ms	17744 KB	Output is correct
41	Incorrect	15 ms	3160 KB	Output isn't correct
42	Halted	0 ms	0 KB	-