oj.uz

Submission #252640

# Submission time Handle Problem Language Result Execution time Memory
252640 2020-07-26T02:34:36 Z khangal Circle selection (APIO18_circle_selection) C++14
7 / 100
 2417 ms 958124 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef double db;
typedef vector<long long> vl;
typedef pair<long long , long long > pl;
const int N=1e6+1;
#define po pop_back
#define pb push_back
#define mk make_pair
#define lw lower_bound
#define up upper_bound
#define ff first
#define ss second
#define boost ios_base::sync_with_stdio(); cin.tie(0); cout.tie(0);
#define MOD 1000000007
#define MAX 1e18 
#define MIN -1e18
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=b;i>=a;i--)
#define con continue
#define freopen freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define PI 3.14159265358979323846264338327950288419716939937510582097494459230781640628
// typedef tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
// template< typename T>
// using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll n,m,ans,mid,mn,mx,cnt,T,sum,h1,h2,e[1234567],b[1234567],c[1234567],d[1<<20],k,i,j,l,h,a[1234567],w,x,y,z;
ll c1[123][123];
bool used[1234567],used1[1234567];
pl p[1234567];
string s,s1[1234567];
map<ll,ll> mp;
map<pl,ll> mpl;
vector<pl> vec,vec1,ansvec;
vector<ll> v[1234567],v1[1234567];
vector<ll> vp[1234567];
set<ll> st;
stack <ll> sta;
set<pl>sp;
struct node{
    ll x,y,r,id;
}str[1234567];
vector<node> conn[1234567];
bool comp(node a,node b){
    if(a.r==b.r)return a.id<b.id;
    return a.r>b.r;
}
ll dist(ll x,ll y){
    return (str[x].x-str[y].x)*(str[x].x-str[y].x)+(str[x].y-str[y].y)*(str[x].y-str[y].y);
}
void connect(ll x){
    rep(i,1,n){
        if(i==x)continue;
        ll tmp=(str[i].r+str[x].r)*(str[i].r+str[x].r);
        if(dist(x , i) <= tmp){
            conn[x].pb(str[i]);
        }
    }
}
void solve(ll ii ,int r){
    for(ll i=mp[p[ii].ff-p[ii].ss];i<=mp[p[ii].ff+p[ii].ss];i++){
        for(auto it : v[i]){
            if(d[it])continue;
            sp.erase({p[it].ss,-it});
            d[it]=r;
 
        }
        for(auto it:v1[i]){
            if(d[it])continue;
            sp.erase({p[it].ss,-it});
            d[it]=r;
        }
    }
}
int main(){
    cin>>n;
    if(n<=5000){
    rep(i,1,n){
        cin>>str[i].x>>str[i].y>>str[i].r;
        str[i].id=i;
    }
    sort(str+1,str+n+1,comp);
    rep(i,1,n){
        connect(i);
    }
    rep(i,1,n){
        if(used[str[i].id]==1)continue;
        used[str[i].id]=1;
        d[str[i].id] = str[i].id;
        for(auto x : conn[i]){
            if(used[x.id]==1)continue;
            d[x.id] = str[i].id;
            used[x.id]=1;
        }
    }
    rep(i,1,n){
        cout<<d[i]<<" ";
    }
    return 0;
    }
    ll xx[1234567],yy[1234567],zz[1234567];
    ll res=0;
    rep(i,1,n){
        cin>>xx[i]>>yy[i]>>zz[i];
        res+=(yy[i]!=yy[1]);
    }
    if(res==0){
    rep(i,1,n){
        p[i] = {xx[i],zz[i]};
        mp[xx[i]+zz[i]]++;mp[xx[i]-zz[i]]++;
    }
    ll cnt=0;
    for(auto it : mp){
        mp[it.ff]=++cnt;
    }
    rep(i,1,n){
        x = mp[p[i].ff-p[i].ss];
        y = mp[p[i].ff+p[i].ss];
        v[x].pb(i);
        v1[y].pb(i);
    }
    rep(i,1,n)
        sp.insert({p[i].ss,-i});
    while(!sp.empty()){
        pl pa = *sp.rbegin();
        pa.ss = -pa.ss;
        solve(pa.ss,pa.ss+1);
    }
    rep(i,1,n)cout<<d[i]<<" ";}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 155000 KB Output is correct
2 Correct 85 ms 154940 KB Output is correct
3 Correct 87 ms 155000 KB Output is correct
4 Correct 84 ms 155012 KB Output is correct
5 Correct 86 ms 155000 KB Output is correct
6 Correct 93 ms 155384 KB Output is correct
7 Correct 88 ms 155388 KB Output is correct
8 Correct 85 ms 155256 KB Output is correct
9 Correct 89 ms 155256 KB Output is correct
10 Correct 90 ms 155384 KB Output is correct
11 Correct 89 ms 155000 KB Output is correct
12 Correct 85 ms 154960 KB Output is correct
13 Correct 92 ms 155000 KB Output is correct
14 Correct 87 ms 155128 KB Output is correct
15 Correct 90 ms 155000 KB Output is correct
16 Correct 106 ms 181380 KB Output is correct
17 Correct 108 ms 178936 KB Output is correct
18 Correct 111 ms 186104 KB Output is correct
19 Correct 884 ms 934296 KB Output is correct
20 Correct 917 ms 958124 KB Output is correct
21 Correct 512 ms 645236 KB Output is correct
22 Correct 145 ms 155384 KB Output is correct
23 Correct 146 ms 155384 KB Output is correct
24 Correct 156 ms 155460 KB Output is correct
25 Correct 145 ms 155384 KB Output is correct
26 Correct 150 ms 155384 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 155000 KB Output is correct
2 Incorrect 266 ms 160140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 155000 KB Output is correct
2 Correct 85 ms 154940 KB Output is correct
3 Correct 87 ms 155000 KB Output is correct
4 Correct 84 ms 155012 KB Output is correct
5 Correct 86 ms 155000 KB Output is correct
6 Correct 93 ms 155384 KB Output is correct
7 Correct 88 ms 155388 KB Output is correct
8 Correct 85 ms 155256 KB Output is correct
9 Correct 89 ms 155256 KB Output is correct
10 Correct 90 ms 155384 KB Output is correct
11 Correct 89 ms 155000 KB Output is correct
12 Correct 85 ms 154960 KB Output is correct
13 Correct 92 ms 155000 KB Output is correct
14 Correct 87 ms 155128 KB Output is correct
15 Correct 90 ms 155000 KB Output is correct
16 Correct 106 ms 181380 KB Output is correct
17 Correct 108 ms 178936 KB Output is correct
18 Correct 111 ms 186104 KB Output is correct
19 Correct 884 ms 934296 KB Output is correct
20 Correct 917 ms 958124 KB Output is correct
21 Correct 512 ms 645236 KB Output is correct
22 Correct 145 ms 155384 KB Output is correct
23 Correct 146 ms 155384 KB Output is correct
24 Correct 156 ms 155460 KB Output is correct
25 Correct 145 ms 155384 KB Output is correct
26 Correct 150 ms 155384 KB Output is correct
27 Incorrect 115 ms 155512 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 155000 KB Output is correct
2 Correct 85 ms 154940 KB Output is correct
3 Correct 87 ms 155000 KB Output is correct
4 Correct 84 ms 155012 KB Output is correct
5 Correct 86 ms 155000 KB Output is correct
6 Correct 93 ms 155384 KB Output is correct
7 Correct 88 ms 155388 KB Output is correct
8 Correct 85 ms 155256 KB Output is correct
9 Correct 89 ms 155256 KB Output is correct
10 Correct 90 ms 155384 KB Output is correct
11 Correct 89 ms 155000 KB Output is correct
12 Correct 85 ms 154960 KB Output is correct
13 Correct 92 ms 155000 KB Output is correct
14 Correct 87 ms 155128 KB Output is correct
15 Correct 90 ms 155000 KB Output is correct
16 Correct 106 ms 181380 KB Output is correct
17 Correct 108 ms 178936 KB Output is correct
18 Correct 111 ms 186104 KB Output is correct
19 Correct 884 ms 934296 KB Output is correct
20 Correct 917 ms 958124 KB Output is correct
21 Correct 512 ms 645236 KB Output is correct
22 Correct 145 ms 155384 KB Output is correct
23 Correct 146 ms 155384 KB Output is correct
24 Correct 156 ms 155460 KB Output is correct
25 Correct 145 ms 155384 KB Output is correct
26 Correct 150 ms 155384 KB Output is correct
27 Incorrect 2417 ms 249968 KB Output isn't correct
28 Halted 0 ms 0 KB -