oj.uz

Submission #937829

# Submission time Handle Problem Language Result Execution time Memory
937829 2024-03-04T15:00:58 Z anton Cell Automaton (JOI23_cell) C++17
4 / 100
 8000 ms 1743000 KB 
#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>
pii delta[4] ={{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

vector<pii> find_adj(pii pos){
    vector<pii> res;
    for(int i = 0; i<4; i++){
        res.push_back({pos.first+delta[i].first, pos.second + delta[i].second});
    }
    return res;
}

map<pii, int> next(map<pii, int> cur){
    map<pii, int> res;
    for(auto e: cur){
        if(e.second >0){
            res[e.first] =e.second-1;
        }
    }

    for(auto e: cur){
        if(e.second ==2){
            for(auto ee: find_adj(e.first)){
                if(res.find(ee)==res.end()){
                    res[ee] = 2;
                }
            }
        }
    }
    return res;
}
const int sz= 10;

void display(map<pii, int>&m){
    for(int i = -sz; i<=sz; i++){
        for(int j = -sz; j<=sz; j++){
            if(m.find({i, j})!=m.end()){
                cout<<m[{i, j}];
            }
            else{
                cout<<"0";
            }
        }
        cout<<endl;
    }
    cout<<endl;
}

signed main(){
    int n, q;
    cin>>n>>q;



    map<pii, int> cur;
    for(int i = 0; i<n; i++){
        int x, y;
        cin>>x>>y;
        cur[{x, y}] = 2;
    }

    vector<map<pii, int>> vc;
    vc.push_back(cur);
    int max_s= 0;


    for(int i = 0; i<q; i++){
        int steps= 0;
        cin>>steps;

        auto qcur = cur;

        for(int j = max_s+1; j<=steps; j++){
            vc.push_back(next(vc.back()));
        }
        max_s=  max(max_s, steps);
        int r= 0;
        for(auto e: vc[steps]){
            if(e.second ==2){
                r++;
            }
        }
        cout<<r<<endl;
    }
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1884 KB Output is correct
2 Correct 9 ms 2904 KB Output is correct
3 Correct 23 ms 4956 KB Output is correct
4 Correct 27 ms 5544 KB Output is correct
5 Correct 8 ms 2140 KB Output is correct
6 Correct 9 ms 2396 KB Output is correct
7 Correct 10 ms 2908 KB Output is correct
8 Correct 48 ms 8124 KB Output is correct
9 Correct 23 ms 5724 KB Output is correct
10 Correct 23 ms 5368 KB Output is correct
11 Correct 21 ms 5212 KB Output is correct
12 Correct 29 ms 6492 KB Output is correct
13 Correct 31 ms 6560 KB Output is correct
14 Correct 28 ms 6748 KB Output is correct
15 Correct 29 ms 6492 KB Output is correct
16 Correct 3 ms 1116 KB Output is correct
17 Correct 5 ms 1372 KB Output is correct
18 Correct 3 ms 1372 KB Output is correct
19 Correct 3 ms 1372 KB Output is correct
20 Correct 5 ms 1372 KB Output is correct
21 Correct 4 ms 1372 KB Output is correct
22 Correct 4 ms 1436 KB Output is correct
23 Correct 4 ms 1372 KB Output is correct
24 Correct 4 ms 1372 KB Output is correct
25 Correct 4 ms 1372 KB Output is correct
26 Correct 4 ms 1412 KB Output is correct
27 Correct 4 ms 1312 KB Output is correct
28 Correct 4 ms 1372 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1884 KB Output is correct
2 Correct 9 ms 2904 KB Output is correct
3 Correct 23 ms 4956 KB Output is correct
4 Correct 27 ms 5544 KB Output is correct
5 Correct 8 ms 2140 KB Output is correct
6 Correct 9 ms 2396 KB Output is correct
7 Correct 10 ms 2908 KB Output is correct
8 Correct 48 ms 8124 KB Output is correct
9 Correct 23 ms 5724 KB Output is correct
10 Correct 23 ms 5368 KB Output is correct
11 Correct 21 ms 5212 KB Output is correct
12 Correct 29 ms 6492 KB Output is correct
13 Correct 31 ms 6560 KB Output is correct
14 Correct 28 ms 6748 KB Output is correct
15 Correct 29 ms 6492 KB Output is correct
16 Correct 3 ms 1116 KB Output is correct
17 Correct 5 ms 1372 KB Output is correct
18 Correct 3 ms 1372 KB Output is correct
19 Correct 3 ms 1372 KB Output is correct
20 Correct 5 ms 1372 KB Output is correct
21 Correct 4 ms 1372 KB Output is correct
22 Correct 4 ms 1436 KB Output is correct
23 Correct 4 ms 1372 KB Output is correct
24 Correct 4 ms 1372 KB Output is correct
25 Correct 4 ms 1372 KB Output is correct
26 Correct 4 ms 1412 KB Output is correct
27 Correct 4 ms 1312 KB Output is correct
28 Correct 4 ms 1372 KB Output is correct
29 Correct 1808 ms 388880 KB Output is correct
30 Correct 2957 ms 619400 KB Output is correct
31 Correct 4429 ms 958048 KB Output is correct
32 Execution timed out 8102 ms 700488 KB Time limit exceeded
33 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8138 ms 1390576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8138 ms 1390576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8167 ms 1743000 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8167 ms 1743000 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1884 KB Output is correct
2 Correct 9 ms 2904 KB Output is correct
3 Correct 23 ms 4956 KB Output is correct
4 Correct 27 ms 5544 KB Output is correct
5 Correct 8 ms 2140 KB Output is correct
6 Correct 9 ms 2396 KB Output is correct
7 Correct 10 ms 2908 KB Output is correct
8 Correct 48 ms 8124 KB Output is correct
9 Correct 23 ms 5724 KB Output is correct
10 Correct 23 ms 5368 KB Output is correct
11 Correct 21 ms 5212 KB Output is correct
12 Correct 29 ms 6492 KB Output is correct
13 Correct 31 ms 6560 KB Output is correct
14 Correct 28 ms 6748 KB Output is correct
15 Correct 29 ms 6492 KB Output is correct
16 Correct 3 ms 1116 KB Output is correct
17 Correct 5 ms 1372 KB Output is correct
18 Correct 3 ms 1372 KB Output is correct
19 Correct 3 ms 1372 KB Output is correct
20 Correct 5 ms 1372 KB Output is correct
21 Correct 4 ms 1372 KB Output is correct
22 Correct 4 ms 1436 KB Output is correct
23 Correct 4 ms 1372 KB Output is correct
24 Correct 4 ms 1372 KB Output is correct
25 Correct 4 ms 1372 KB Output is correct
26 Correct 4 ms 1412 KB Output is correct
27 Correct 4 ms 1312 KB Output is correct
28 Correct 4 ms 1372 KB Output is correct
29 Correct 1808 ms 388880 KB Output is correct
30 Correct 2957 ms 619400 KB Output is correct
31 Correct 4429 ms 958048 KB Output is correct
32 Execution timed out 8102 ms 700488 KB Time limit exceeded
33 Halted 0 ms 0 KB -