답안 #742300

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
742300	2023-05-16T05:06:22 Z	victor_gao	원 고르기 (APIO18_circle_selection)	C++17	7 / 100	3000 ms	23892 KB

circle_selection

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 300015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
struct circle{
    int x,y,r,i;
    circle(int a=0,int b=0,int c=0,int d=0):x(a),y(b),r(c),i(d){}
    bool operator<(const circle a)const{
        if (r!=a.r) return r<a.r;
        else return i>a.i;
    }
    bool intersect(circle c){
        int dis=(c.x-x)*(c.x-x)+(c.y-y)*(c.y-y);
        return dis<=(r+c.r)*(r+c.r);
    }
};
int n,ans[N];
vector<circle>all;
set<int>st;
signed main(){
    fast
    cin>>n;
    for (int i=1;i<=n;i++){
        int a,b,c; cin>>a>>b>>c;
        all.push_back(circle(a,b,c,i));
    }
    sort(all.begin(),all.end());
    while (!all.empty()){
        circle now=all.back(); all.pop_back();
        if (ans[now.i]) continue;
        ans[now.i]=now.i;
        for (auto i:all){
            if (ans[i.i]) continue;
            if (now.intersect(i)){
                ans[i.i]=now.i;
                continue;
            }
        }
    }
    for (int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    cout<<'\n';
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	212 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	332 KB	Output is correct
9	Correct	1 ms	328 KB	Output is correct
10	Correct	0 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	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	328 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	468 KB	Output is correct
19	Correct	3 ms	856 KB	Output is correct
20	Correct	3 ms	860 KB	Output is correct
21	Correct	3 ms	980 KB	Output is correct
22	Correct	21 ms	852 KB	Output is correct
23	Correct	20 ms	852 KB	Output is correct
24	Correct	20 ms	848 KB	Output is correct
25	Correct	20 ms	800 KB	Output is correct
26	Correct	21 ms	848 KB	Output is correct

Subtask #2
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	142 ms	22956 KB	Output is correct
2	Correct	139 ms	22816 KB	Output is correct
3	Correct	134 ms	22760 KB	Output is correct
4	Correct	134 ms	22912 KB	Output is correct
5	Execution timed out	3064 ms	20992 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Execution timed out	3058 ms	7268 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	3056 ms	23892 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	212 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	332 KB	Output is correct
9	Correct	1 ms	328 KB	Output is correct
10	Correct	0 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	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	328 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	468 KB	Output is correct
19	Correct	3 ms	856 KB	Output is correct
20	Correct	3 ms	860 KB	Output is correct
21	Correct	3 ms	980 KB	Output is correct
22	Correct	21 ms	852 KB	Output is correct
23	Correct	20 ms	852 KB	Output is correct
24	Correct	20 ms	848 KB	Output is correct
25	Correct	20 ms	800 KB	Output is correct
26	Correct	21 ms	848 KB	Output is correct
27	Correct	5 ms	1240 KB	Output is correct
28	Correct	6 ms	1248 KB	Output is correct
29	Correct	5 ms	1240 KB	Output is correct
30	Correct	78 ms	1240 KB	Output is correct
31	Correct	78 ms	1240 KB	Output is correct
32	Correct	92 ms	1248 KB	Output is correct
33	Correct	46 ms	7972 KB	Output is correct
34	Correct	48 ms	8056 KB	Output is correct
35	Correct	49 ms	7932 KB	Output is correct
36	Execution timed out	3069 ms	6868 KB	Time limit exceeded
37	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	212 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	332 KB	Output is correct
9	Correct	1 ms	328 KB	Output is correct
10	Correct	0 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	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	328 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	468 KB	Output is correct
19	Correct	3 ms	856 KB	Output is correct
20	Correct	3 ms	860 KB	Output is correct
21	Correct	3 ms	980 KB	Output is correct
22	Correct	21 ms	852 KB	Output is correct
23	Correct	20 ms	852 KB	Output is correct
24	Correct	20 ms	848 KB	Output is correct
25	Correct	20 ms	800 KB	Output is correct
26	Correct	21 ms	848 KB	Output is correct
27	Correct	142 ms	22956 KB	Output is correct
28	Correct	139 ms	22816 KB	Output is correct
29	Correct	134 ms	22760 KB	Output is correct
30	Correct	134 ms	22912 KB	Output is correct
31	Execution timed out	3064 ms	20992 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

답안 #742300

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 0 / 12.0

Subtask #3 0 / 15.0

Subtask #4 0 / 23.0

Subtask #5 0 / 30.0

Subtask #6 0 / 13.0

Subtask #1
7.0 / 7.0

Subtask #2
0 / 12.0

Subtask #3
0 / 15.0

Subtask #4
0 / 23.0

Subtask #5
0 / 30.0

Subtask #6
0 / 13.0