oj.uz

Submission #744536

# Submission time Handle Problem Language Result Execution time Memory
744536 2023-05-18T17:09:23 Z Abito Circle selection (APIO18_circle_selection) C++14
19 / 100
 1321 ms 240244 KB 
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define ep insert
#define pow pwr
#define sqrt sqrtt
#define elif else if
#define y1 YONE
#define int long long
using namespace std;
struct circle{
    int x,y,r,idx;
};
bool cmp1(circle x,circle y){
    if (x.r!=y.r) return x.r>y.r;
    return x.idx<y.idx;
}
int dis(int x1,int y1,int x2,int y2){
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
bool cmp2(pair<pair<int,int>,int> x,pair<pair<int,int>,int> y){
    if (x.F.S-x.F.F!=y.F.S-y.F.F) return x.F.S-x.F.F>y.F.S-y.F.F;
    return x.S<y.S;
}
const int N=1e6+5;
int n,ans[N];
pair<pair<int,int>,int> a[N];
vector<int> adj[N];
map<int,int> mp;
circle b[N];
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n;
    if (n>5000){
    for (int i=1;i<=n;i++){
        int x,y,r;
        cin>>x>>y>>r;
        a[i]={{x-r,x+r},i};
        mp[x+r]++;
        mp[x-r]++;
    }
    sort(a+1,a+1+n,cmp2);
    int c=0;
    for (auto u:mp){
        c++;
        mp[u.F]=c;
    }
    for (int i=1;i<=n;i++){
        a[i].F={mp[a[i].F.F],mp[a[i].F.S]};
        adj[a[i].F.F].pb(i);
        adj[a[i].F.S].pb(i);
    }
    for (int i=1;i<=n;i++){
        if (ans[a[i].S]) continue;
        for (int j=a[i].F.F;j<=a[i].F.S;j++){
            for (auto u:adj[j]){
                if (!ans[a[u].S]) ans[a[u].S]=a[i].S;
            }adj[j].clear();
        }
    }
    for (int i=1;i<=n;i++) cout<<ans[i]<<' ';return 0;}
    for (int i=1;i<=n;i++) {cin>>b[i].x>>b[i].y>>b[i].r;b[i].idx=i;}
    sort(b+1,b+1+n,cmp1);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            int x=dis(b[i].x,b[i].y,b[j].x,b[j].y),y=(b[i].r+b[j].r)*(b[i].r+b[j].r);
            if (x>y) continue;
            adj[i].pb(j);
        }
    }
    for (int i=1;i<=n;i++){
        if (ans[b[i].idx]) continue;
        for (auto u:adj[i]){
            if (ans[b[u].idx]) continue;
            ans[b[u].idx]=b[i].idx;
        }
    }
    for (int i=1;i<=n;i++) cout<<ans[i]<<' ';
    return 0;
}

Compilation message

circle_selection.cpp: In function 'int32_t main()':
circle_selection.cpp:63:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   63 |     for (int i=1;i<=n;i++) cout<<ans[i]<<' ';return 0;}
      |     ^~~
circle_selection.cpp:63:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   63 |     for (int i=1;i<=n;i++) cout<<ans[i]<<' ';return 0;}
      |                                              ^~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 15 ms 23736 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 16 ms 23824 KB Output is correct
5 Correct 13 ms 23824 KB Output is correct
6 Correct 13 ms 23892 KB Output is correct
7 Correct 14 ms 23824 KB Output is correct
8 Correct 15 ms 23892 KB Output is correct
9 Correct 13 ms 23828 KB Output is correct
10 Correct 14 ms 23804 KB Output is correct
11 Correct 12 ms 23824 KB Output is correct
12 Correct 13 ms 23764 KB Output is correct
13 Correct 13 ms 23764 KB Output is correct
14 Correct 14 ms 23764 KB Output is correct
15 Correct 13 ms 23928 KB Output is correct
16 Correct 23 ms 31308 KB Output is correct
17 Correct 25 ms 30828 KB Output is correct
18 Correct 29 ms 31828 KB Output is correct
19 Correct 239 ms 234660 KB Output is correct
20 Correct 204 ms 240244 KB Output is correct
21 Correct 237 ms 157904 KB Output is correct
22 Correct 92 ms 24220 KB Output is correct
23 Correct 93 ms 24240 KB Output is correct
24 Correct 112 ms 24252 KB Output is correct
25 Correct 100 ms 24204 KB Output is correct
26 Correct 94 ms 24272 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1263 ms 91604 KB Output is correct
2 Correct 1229 ms 91560 KB Output is correct
3 Correct 1321 ms 91324 KB Output is correct
4 Correct 1285 ms 91732 KB Output is correct
5 Correct 991 ms 63852 KB Output is correct
6 Correct 1032 ms 90788 KB Output is correct
7 Correct 1113 ms 85320 KB Output is correct
8 Correct 1018 ms 87772 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Incorrect 286 ms 47408 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 15 ms 23736 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 16 ms 23824 KB Output is correct
5 Correct 13 ms 23824 KB Output is correct
6 Correct 13 ms 23892 KB Output is correct
7 Correct 14 ms 23824 KB Output is correct
8 Correct 15 ms 23892 KB Output is correct
9 Correct 13 ms 23828 KB Output is correct
10 Correct 14 ms 23804 KB Output is correct
11 Correct 12 ms 23824 KB Output is correct
12 Correct 13 ms 23764 KB Output is correct
13 Correct 13 ms 23764 KB Output is correct
14 Correct 14 ms 23764 KB Output is correct
15 Correct 13 ms 23928 KB Output is correct
16 Correct 23 ms 31308 KB Output is correct
17 Correct 25 ms 30828 KB Output is correct
18 Correct 29 ms 31828 KB Output is correct
19 Correct 239 ms 234660 KB Output is correct
20 Correct 204 ms 240244 KB Output is correct
21 Correct 237 ms 157904 KB Output is correct
22 Correct 92 ms 24220 KB Output is correct
23 Correct 93 ms 24240 KB Output is correct
24 Correct 112 ms 24252 KB Output is correct
25 Correct 100 ms 24204 KB Output is correct
26 Correct 94 ms 24272 KB Output is correct
27 Incorrect 28 ms 26316 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 15 ms 23736 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 16 ms 23824 KB Output is correct
5 Correct 13 ms 23824 KB Output is correct
6 Correct 13 ms 23892 KB Output is correct
7 Correct 14 ms 23824 KB Output is correct
8 Correct 15 ms 23892 KB Output is correct
9 Correct 13 ms 23828 KB Output is correct
10 Correct 14 ms 23804 KB Output is correct
11 Correct 12 ms 23824 KB Output is correct
12 Correct 13 ms 23764 KB Output is correct
13 Correct 13 ms 23764 KB Output is correct
14 Correct 14 ms 23764 KB Output is correct
15 Correct 13 ms 23928 KB Output is correct
16 Correct 23 ms 31308 KB Output is correct
17 Correct 25 ms 30828 KB Output is correct
18 Correct 29 ms 31828 KB Output is correct
19 Correct 239 ms 234660 KB Output is correct
20 Correct 204 ms 240244 KB Output is correct
21 Correct 237 ms 157904 KB Output is correct
22 Correct 92 ms 24220 KB Output is correct
23 Correct 93 ms 24240 KB Output is correct
24 Correct 112 ms 24252 KB Output is correct
25 Correct 100 ms 24204 KB Output is correct
26 Correct 94 ms 24272 KB Output is correct
27 Correct 1263 ms 91604 KB Output is correct
28 Correct 1229 ms 91560 KB Output is correct
29 Correct 1321 ms 91324 KB Output is correct
30 Correct 1285 ms 91732 KB Output is correct
31 Correct 991 ms 63852 KB Output is correct
32 Correct 1032 ms 90788 KB Output is correct
33 Correct 1113 ms 85320 KB Output is correct
34 Correct 1018 ms 87772 KB Output is correct
35 Correct 13 ms 23764 KB Output is correct
36 Incorrect 286 ms 47408 KB Output isn't correct
37 Halted 0 ms 0 KB -