oj.uz

Submission #552531

# Submission time Handle Problem Language Result Execution time Memory
552531 2022-04-23T09:25:17 Z zaneyu Circle selection (APIO18_circle_selection) C++14
7 / 100
 3000 ms 17400 KB 
/*input
11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1
*/
#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
const int maxn=3e5+5;
#define pb push_back
#define lowb(x) x&(-x)
#define ll long long
#define MNTO(x,y) x=min(x,y)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define pii pair<ll,ll>
#define f first
#define s second
pair<pii,ll> arr[maxn];
inline bool inter(int a,int b){
    ll d=(arr[a].f.s-arr[b].f.s)*(arr[a].f.s-arr[b].f.s)+(arr[a].f.f-arr[b].f.f)*(arr[a].f.f-arr[b].f.f);
    return d<=(arr[a].s+arr[b].s)*(arr[a].s+arr[b].s);
}
bool ok[maxn];
int ans[maxn];
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n;
    cin>>n;
    vector<int> v;
    REP(i,n) cin>>arr[i].f.f>>arr[i].f.s>>arr[i].s,v.pb(i);
    REP(i,n){
        int p=-1;
        for(int j:v){
            if(ok[j]) continue;
            if(p==-1 or arr[p].s<arr[j].s) p=j;
        }
        if(p==-1) break;
        vector<int> nv;
        for(int j:v){
            if(inter(j,p)) ans[j]=p,ok[j]=1;
            else nv.pb(j);
        }
        v=nv;
    }
    REP(i,n){
        cout<<ans[i]+1<<' ';
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 324 KB Output is correct
14 Correct 1 ms 324 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 3 ms 596 KB Output is correct
20 Correct 3 ms 632 KB Output is correct
21 Correct 3 ms 596 KB Output is correct
22 Correct 87 ms 672 KB Output is correct
23 Correct 88 ms 672 KB Output is correct
24 Correct 103 ms 688 KB Output is correct
25 Correct 99 ms 672 KB Output is correct
26 Correct 88 ms 604 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 14436 KB Output is correct
2 Correct 138 ms 16292 KB Output is correct
3 Correct 127 ms 16448 KB Output is correct
4 Correct 106 ms 16404 KB Output is correct
5 Execution timed out 3063 ms 17400 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Execution timed out 3030 ms 6008 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 3053 ms 14460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 324 KB Output is correct
14 Correct 1 ms 324 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 3 ms 596 KB Output is correct
20 Correct 3 ms 632 KB Output is correct
21 Correct 3 ms 596 KB Output is correct
22 Correct 87 ms 672 KB Output is correct
23 Correct 88 ms 672 KB Output is correct
24 Correct 103 ms 688 KB Output is correct
25 Correct 99 ms 672 KB Output is correct
26 Correct 88 ms 604 KB Output is correct
27 Correct 8 ms 980 KB Output is correct
28 Correct 5 ms 972 KB Output is correct
29 Correct 5 ms 980 KB Output is correct
30 Correct 384 ms 1016 KB Output is correct
31 Correct 357 ms 1016 KB Output is correct
32 Correct 406 ms 1028 KB Output is correct
33 Correct 41 ms 7356 KB Output is correct
34 Correct 52 ms 7348 KB Output is correct
35 Correct 47 ms 7220 KB Output is correct
36 Execution timed out 3074 ms 6992 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 324 KB Output is correct
14 Correct 1 ms 324 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 3 ms 596 KB Output is correct
20 Correct 3 ms 632 KB Output is correct
21 Correct 3 ms 596 KB Output is correct
22 Correct 87 ms 672 KB Output is correct
23 Correct 88 ms 672 KB Output is correct
24 Correct 103 ms 688 KB Output is correct
25 Correct 99 ms 672 KB Output is correct
26 Correct 88 ms 604 KB Output is correct
27 Correct 115 ms 14436 KB Output is correct
28 Correct 138 ms 16292 KB Output is correct
29 Correct 127 ms 16448 KB Output is correct
30 Correct 106 ms 16404 KB Output is correct
31 Execution timed out 3063 ms 17400 KB Time limit exceeded
32 Halted 0 ms 0 KB -