oj.uz

Submission #123974

# Submission time Handle Problem Language Result Execution time Memory
123974 2019-07-02T10:19:54 Z RayanLabidi Circle selection (APIO18_circle_selection) C++14
7 / 100
 3000 ms 1048580 KB 
#include <bits/stdc++.h>
#define rp(_s,_i,_n) for(int _s=_i;_s<_n;_s++)
#define sz(_itt) (int)_itt.size()
#define mp(__a,__b) make_pair(__a,__b)
#define pb(_p) push_back(_p)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define int long long
using namespace std;
typedef long long ll;

struct cir{
    int rad,ind,x,y;
};
bool acomp(cir a,cir b){
    if(a.rad==b.rad)return a.ind<b.ind;
    return a.rad>b.rad;
}
vector<cir> c;//circles
vector<vector<cir> >con;//circles connected to circle con[i]
int n;//numb of circles
vector<bool>del;
vector<int> killer;
ll dist(int x,int y){
    return (c[x].x-c[y].x)*(c[x].x-c[y].x)+(c[x].y-c[y].y)*(c[x].y-c[y].y);
}
void connecting(int u){
    rp(i,0,n){
        if(i==u)continue;
        ll temp=(c[i].rad+c[u].rad)*(c[i].rad+c[u].rad)*1LL;
        if(dist(u,i)<=temp){
            con[u].push_back(c[i]);
        }
    }
}
int32_t main()
{
    fastio

    cin>>n;
    c.resize(n),con.resize(n),del.resize(n),killer.resize(n);
    rp(i,0,n){
        cin>>c[i].x>>c[i].y>>c[i].rad;
        c[i].ind=i;
    }
    sort(c.begin(),c.end(),acomp);
    rp(i,0,n){
        connecting(i);
    }
    rp(i,0,n){
        if(del[c[i].ind]==1)continue;
        del[c[i].ind]=1;
        killer[c[i].ind]=c[i].ind;
        for(auto x:con[i]){
            if(del[x.ind]==1)continue;
            killer[x.ind]=c[i].ind;
            del[x.ind]=1;
        }
    }
    rp(i,0,n){
        cout <<killer[i]+1<<" ";
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 380 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 35 ms 26808 KB Output is correct
17 Correct 34 ms 24572 KB Output is correct
18 Correct 37 ms 31796 KB Output is correct
19 Correct 1263 ms 779608 KB Output is correct
20 Correct 1317 ms 803592 KB Output is correct
21 Correct 689 ms 490376 KB Output is correct
22 Correct 74 ms 860 KB Output is correct
23 Correct 77 ms 760 KB Output is correct
24 Correct 74 ms 760 KB Output is correct
25 Correct 74 ms 836 KB Output is correct
26 Correct 74 ms 860 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 2762 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 416 KB Output is correct
2 Execution timed out 3096 ms 9456 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 380 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 35 ms 26808 KB Output is correct
17 Correct 34 ms 24572 KB Output is correct
18 Correct 37 ms 31796 KB Output is correct
19 Correct 1263 ms 779608 KB Output is correct
20 Correct 1317 ms 803592 KB Output is correct
21 Correct 689 ms 490376 KB Output is correct
22 Correct 74 ms 860 KB Output is correct
23 Correct 77 ms 760 KB Output is correct
24 Correct 74 ms 760 KB Output is correct
25 Correct 74 ms 836 KB Output is correct
26 Correct 74 ms 860 KB Output is correct
27 Runtime error 1210 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 380 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 35 ms 26808 KB Output is correct
17 Correct 34 ms 24572 KB Output is correct
18 Correct 37 ms 31796 KB Output is correct
19 Correct 1263 ms 779608 KB Output is correct
20 Correct 1317 ms 803592 KB Output is correct
21 Correct 689 ms 490376 KB Output is correct
22 Correct 74 ms 860 KB Output is correct
23 Correct 77 ms 760 KB Output is correct
24 Correct 74 ms 760 KB Output is correct
25 Correct 74 ms 836 KB Output is correct
26 Correct 74 ms 860 KB Output is correct
27 Runtime error 2762 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Halted 0 ms 0 KB -