oj.uz

Submission #965192

# Submission time Handle Problem Language Result Execution time Memory
965192 2024-04-18T08:10:24 Z phoenix0423 Cell Automaton (JOI23_cell) C++17
0 / 100
 66 ms 12528 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int maxn = 4000 + 5;
const int INF = 1e18;
int dist[maxn][maxn];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int n, q;

void sol1(vector<pll> e){
    queue<pll> qq;
    for(int i = 0; i < maxn; i++) for(int j = 0; j < maxn; j++) dist[i][j] = INF;
    for(auto [x, y] : e){
        x += maxn / 2, y += maxn / 2;
        dist[x][y] = 0;
        qq.push({x, y});
    }
    vector<int> ans(maxn * 2);
    ans[0] = e.size();
    auto inbound = [&](int x, int y) -> bool {
        return x >= 0 && y >= 0 && x < maxn && y < maxn;
    };
    while(!qq.empty()){
        auto [x, y] = qq.front(); qq.pop();
        for(int d = 0; d < 4; d++){
            int xx = x + dx[d], yy = y + dy[d];
            if(!inbound(xx, yy) || dist[xx][yy] < INF) continue;
            dist[xx][yy] = dist[x][y] + 1;
            ans[dist[xx][yy]] += 1;
            qq.push({xx, yy});
        }
    }
    for(int i = 0; i < q; i++){
        int t;
        cin>>t;
        cout<<ans[t]<<"\n";
    }
    return;
}

signed main(void){
    fastio;
    cin>>n>>q;
    int mx = 0;
    vector<pll> e;
    for(int i = 0; i < n; i++){
        int x, y;
        cin>>x>>y;
        mx = max(mx, max(abs(x), abs(y)));
        e.pb({x, y});
    }
    if(mx < 0){
        sol1(e);
        return 0;
    }
    sort(e.begin(), e.end());
    vector<int> dist;
    for(int i = 1; i < n; i++) dist.pb(e[i].f - e[i - 1].f);
    sort(dist.begin(), dist.end());
    for(auto x : dist) cout<<x<<" ";
    cout<<"\n";
    int id = 0;
    int comp = n, face = n * 4, ans = n;
    int prv = 0;
    vector<pll> op;
    for(auto x : dist) op.pb({x, -1}), op.pb({x, 2});
    for(int i = 0; i < q; i++){
        int x;
        cin>>x;
        op.pb({x, 1});
    }
    sort(op.begin(), op.end());
    for(auto [t, val] : op){
        ans += face * (t - prv);
        if(prv == 0 && t != 0) ans -= n;
        prv = t;
        if(val != 1){
            ans -= (t + 1);
            if(val == 2) ans += 2;
            face -= 2;
        }
        else cout<<ans<<"\n";
    }


}

Compilation message

cell.cpp: In function 'int main()':
cell.cpp:72:9: warning: unused variable 'id' [-Wunused-variable]
   72 |     int id = 0;
      |         ^~
cell.cpp:73:9: warning: unused variable 'comp' [-Wunused-variable]
   73 |     int comp = n, face = n * 4, ans = n;
      |         ^~~~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 12528 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 604 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 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

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