oj.uz

Submission #937838

# Submission time Handle Problem Language Result Execution time Memory
937838 2024-03-04T15:09:38 Z anton Cell Automaton (JOI23_cell) C++17
16 / 100
 8000 ms 979120 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<int> ans(1000+1, -1);
    int r;

    for(int steps=  0; steps<1000+1; steps++){
        r=0;
        for(auto e: cur){
            if(e.second ==2){
                r++;
            }
        }
        ans[steps] = r;
        cur = next(cur);
    }
    int max_s= 0;




    for(int i = 0; i<q; i++){
        int steps= 0;
        cin>>steps;
        cout<<ans[steps]<<endl;
    }
    
}

Compilation message

cell.cpp: In function 'int main()':
cell.cpp:78:9: warning: unused variable 'max_s' [-Wunused-variable]
   78 |     int max_s= 0;
      |         ^~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1497 ms 2724 KB Output is correct
2 Correct 1532 ms 2740 KB Output is correct
3 Correct 1700 ms 2996 KB Output is correct
4 Correct 1766 ms 2808 KB Output is correct
5 Correct 1519 ms 2636 KB Output is correct
6 Correct 1540 ms 2736 KB Output is correct
7 Correct 1623 ms 2632 KB Output is correct
8 Correct 1846 ms 2828 KB Output is correct
9 Correct 1772 ms 2640 KB Output is correct
10 Correct 1809 ms 3112 KB Output is correct
11 Correct 1808 ms 3092 KB Output is correct
12 Correct 1808 ms 3056 KB Output is correct
13 Correct 1821 ms 2920 KB Output is correct
14 Correct 1804 ms 2680 KB Output is correct
15 Correct 1808 ms 3048 KB Output is correct
16 Correct 1457 ms 2852 KB Output is correct
17 Correct 1447 ms 2708 KB Output is correct
18 Correct 1487 ms 2612 KB Output is correct
19 Correct 1476 ms 2556 KB Output is correct
20 Correct 1458 ms 2932 KB Output is correct
21 Correct 1480 ms 2640 KB Output is correct
22 Correct 1468 ms 2744 KB Output is correct
23 Correct 1435 ms 2640 KB Output is correct
24 Correct 1467 ms 2660 KB Output is correct
25 Correct 1448 ms 2636 KB Output is correct
26 Correct 1490 ms 2896 KB Output is correct
27 Correct 1480 ms 2628 KB Output is correct
28 Correct 1444 ms 2680 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1497 ms 2724 KB Output is correct
2 Correct 1532 ms 2740 KB Output is correct
3 Correct 1700 ms 2996 KB Output is correct
4 Correct 1766 ms 2808 KB Output is correct
5 Correct 1519 ms 2636 KB Output is correct
6 Correct 1540 ms 2736 KB Output is correct
7 Correct 1623 ms 2632 KB Output is correct
8 Correct 1846 ms 2828 KB Output is correct
9 Correct 1772 ms 2640 KB Output is correct
10 Correct 1809 ms 3112 KB Output is correct
11 Correct 1808 ms 3092 KB Output is correct
12 Correct 1808 ms 3056 KB Output is correct
13 Correct 1821 ms 2920 KB Output is correct
14 Correct 1804 ms 2680 KB Output is correct
15 Correct 1808 ms 3048 KB Output is correct
16 Correct 1457 ms 2852 KB Output is correct
17 Correct 1447 ms 2708 KB Output is correct
18 Correct 1487 ms 2612 KB Output is correct
19 Correct 1476 ms 2556 KB Output is correct
20 Correct 1458 ms 2932 KB Output is correct
21 Correct 1480 ms 2640 KB Output is correct
22 Correct 1468 ms 2744 KB Output is correct
23 Correct 1435 ms 2640 KB Output is correct
24 Correct 1467 ms 2660 KB Output is correct
25 Correct 1448 ms 2636 KB Output is correct
26 Correct 1490 ms 2896 KB Output is correct
27 Correct 1480 ms 2628 KB Output is correct
28 Correct 1444 ms 2680 KB Output is correct
29 Correct 1489 ms 2720 KB Output is correct
30 Correct 2469 ms 3704 KB Output is correct
31 Correct 3909 ms 4480 KB Output is correct
32 Correct 7562 ms 131760 KB Output is correct
33 Correct 2518 ms 3500 KB Output is correct
34 Correct 2965 ms 3944 KB Output is correct
35 Correct 2983 ms 3824 KB Output is correct
36 Correct 1438 ms 2892 KB Output is correct
37 Correct 1470 ms 2660 KB Output is correct
38 Correct 6389 ms 21844 KB Output is correct
39 Correct 6333 ms 66176 KB Output is correct
40 Correct 7648 ms 148700 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8122 ms 979120 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 8122 ms 979120 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 8061 ms 9100 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 8061 ms 9100 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1497 ms 2724 KB Output is correct
2 Correct 1532 ms 2740 KB Output is correct
3 Correct 1700 ms 2996 KB Output is correct
4 Correct 1766 ms 2808 KB Output is correct
5 Correct 1519 ms 2636 KB Output is correct
6 Correct 1540 ms 2736 KB Output is correct
7 Correct 1623 ms 2632 KB Output is correct
8 Correct 1846 ms 2828 KB Output is correct
9 Correct 1772 ms 2640 KB Output is correct
10 Correct 1809 ms 3112 KB Output is correct
11 Correct 1808 ms 3092 KB Output is correct
12 Correct 1808 ms 3056 KB Output is correct
13 Correct 1821 ms 2920 KB Output is correct
14 Correct 1804 ms 2680 KB Output is correct
15 Correct 1808 ms 3048 KB Output is correct
16 Correct 1457 ms 2852 KB Output is correct
17 Correct 1447 ms 2708 KB Output is correct
18 Correct 1487 ms 2612 KB Output is correct
19 Correct 1476 ms 2556 KB Output is correct
20 Correct 1458 ms 2932 KB Output is correct
21 Correct 1480 ms 2640 KB Output is correct
22 Correct 1468 ms 2744 KB Output is correct
23 Correct 1435 ms 2640 KB Output is correct
24 Correct 1467 ms 2660 KB Output is correct
25 Correct 1448 ms 2636 KB Output is correct
26 Correct 1490 ms 2896 KB Output is correct
27 Correct 1480 ms 2628 KB Output is correct
28 Correct 1444 ms 2680 KB Output is correct
29 Correct 1489 ms 2720 KB Output is correct
30 Correct 2469 ms 3704 KB Output is correct
31 Correct 3909 ms 4480 KB Output is correct
32 Correct 7562 ms 131760 KB Output is correct
33 Correct 2518 ms 3500 KB Output is correct
34 Correct 2965 ms 3944 KB Output is correct
35 Correct 2983 ms 3824 KB Output is correct
36 Correct 1438 ms 2892 KB Output is correct
37 Correct 1470 ms 2660 KB Output is correct
38 Correct 6389 ms 21844 KB Output is correct
39 Correct 6333 ms 66176 KB Output is correct
40 Correct 7648 ms 148700 KB Output is correct
41 Execution timed out 8122 ms 979120 KB Time limit exceeded
42 Halted 0 ms 0 KB -