oj.uz

Submission #364616

# Submission time Handle Problem Language Result Execution time Memory
364616 2021-02-09T14:47:57 Z doowey Circle selection (APIO18_circle_selection) C++14
0 / 100
 133 ms 64484 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)3e5 + 10;
ll cut = (1ll << 31);
int sol[N];
ll xi[N];
ll yi[N];
ll ri[N];

ll sq(ll v){
    return v * 1ll * v;
}

bool check(int i, int j){
    // sqrt((xi-xj)^2+(yi-yj)^2) <= (ri + rj)
    ll val = sq(xi[i] - xi[j]) + sq(yi[i] - yi[j]);
    ll cmp = sq(ri[i] + ri[j]);
    if(val <= cmp)
        return true;
    return false;
}

map<pii, int> idx;
set<int> V[N];
int cid;

void add(pii x){
    if(idx.count(x)) return;
    idx[x]=cid;
    cid++;
}

int main(){
    fastIO;
    freopen("in.txt","r",stdin);
    int n;
    cin >> n;
    vector<pii> cir;
    for(int i = 1; i <= n; i ++ ){
        cin >> xi[i] >> yi[i] >> ri[i];
        cir.push_back({ri[i], -i});
    }
    sort(cir.begin(), cir.end());
    int id;
    bool has;
    ll ci, cj;
    int gg;
    for(int i = cir.size() - 1; i >= 0 ;i -- ){
        id = -cir[i].se;
        if(sol[id] == 0){
            has=false;
            while(cut/2ll >= ri[id]){
                has=true;
                cut /= 2ll;
            }

            if(has){
                idx.clear();
                for(int i = 0 ; i < cid; i ++ ){
                    V[i].clear();
                }
                cid = 0;
                for(int i = 1; i <= n; i ++ ){
                    if(sol[i] == 0){
                        add(mp(xi[i]/cut, yi[i]/cut));
                        V[idx[mp(xi[i]/cut,yi[i]/cut)]].insert(i);
                    }
                }
            }
            ci = xi[id]/cut;
            cj = yi[id]/cut;
            for(ll p = -2; p <= 2; p ++ ){
                for(ll q = -2 ; q <= 2; q ++ ){
                    if(idx.count(mp(ci+p,cj+q))){
                        gg = idx[mp(ci + p, cj + q)];
                        auto it = V[gg].begin();
                        while(it != V[gg].end()){
                            if(check(*it,id)){
                                sol[*it]=id;
                                it=V[gg].erase(it);
                            }
                            else{
                                it ++ ;
                            }
                        }
                    }
                }
            }
        }
    }
    for(int i = 1; i <= n; i ++ ){
        cout << sol[i] << " ";
    }
    cout << "\n";
    return 0;
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:45:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   45 |     freopen("in.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 112 ms 64272 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 133 ms 64272 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 110 ms 64484 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 111 ms 64272 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 112 ms 64272 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 112 ms 64272 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -