Submission #1092213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092213		onlk97	Cell Automaton (JOI23_cell)	C++14	16 / 100	3377 ms	17748 KiB

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 / 4
• Subtask 2: 12 / 12
• Subtask 3: 0 / 8
• Subtask 4: 0 / 8
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 26