답안 #59939 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59939	2018-07-23T10:59:38 Z	Flugan42	원 고르기 (APIO18_circle_selection)	C++14	19 / 100	928 ms	49644 KB

circle_selection

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
#define rep(i,a,b) for(int i = a; i < b; i++)
#define per(i,a,b) for(int i = a; i >= b; i--)
#define inf 1000000000000000000
#define sz(x) (ll)(x).size()
#define all(x) x.begin(),x.end()

struct circle {
  ll x,y,r,id;
} ;
vector< circle > inp;
vi vis;
vii endp,endpy;
circle _;
ll n;

bool mysort(circle a, circle b){
  if (a.r == b.r) return a.id < b.id;
  return a.r > b.r;
}

ld dist(ll i, ll j){
  ll dx = inp[i].x-inp[j].x, dy = inp[i].y-inp[j].y;
  return sqrt(ld(dx*dx)+ld(dy*dy));
}

int main(){
  cin >> n; inp.assign(n,_);
  rep(i,0,n){
    cin >> inp[i].x >> inp[i].y >> inp[i].r;
    inp[i].id = i;
  }
  sort(all(inp),mysort);
  rep(i,0,n){
    endp.push_back(make_pair(inp[i].x-inp[i].r,i));
    endp.push_back(make_pair(inp[i].x+inp[i].r,i));
    endpy.push_back(make_pair(inp[i].y-inp[i].r,i));
    endpy.push_back(make_pair(inp[i].y+inp[i].r,i));
  }
  sort(all(endp));

  if (n <= 10000){
    vis.assign(n,-1);
    rep(i,0,n){
      if (vis[i] != -1) continue;
      rep(j,0,n){
        if (vis[j] != -1) continue;
        if (dist(i,j) <= inp[i].r+inp[j].r) vis[j] = inp[i].id;
      }
    }
  } else {
    vis.assign(n,-1);
    rep(i,0,n){
      if (vis[i] != -1) continue;
      ll lo = lower_bound(all(endp),make_pair(inp[i].x-inp[i].r,0LL))-endp.begin();
      while (0 <= lo && lo < sz(endp) && endp[lo].first <= inp[i].x+inp[i].r){
        if (vis[endp[lo].second] == -1) vis[endp[lo].second] = inp[i].id;
        lo++;
      }
    }
  }
  vi res; res.assign(n,0);
  rep(i,0,n){
    res[inp[i].id] = vis[i];
  }
  rep(i,0,n) cout << res[i]+1 << " ";
  cout << endl;
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	3 ms	432 KB	Output is correct
4	Correct	2 ms	480 KB	Output is correct
5	Correct	2 ms	556 KB	Output is correct
6	Correct	3 ms	712 KB	Output is correct
7	Correct	2 ms	712 KB	Output is correct
8	Correct	3 ms	712 KB	Output is correct
9	Correct	3 ms	712 KB	Output is correct
10	Correct	2 ms	712 KB	Output is correct
11	Correct	2 ms	712 KB	Output is correct
12	Correct	3 ms	712 KB	Output is correct
13	Correct	3 ms	712 KB	Output is correct
14	Correct	3 ms	712 KB	Output is correct
15	Correct	2 ms	752 KB	Output is correct
16	Correct	5 ms	752 KB	Output is correct
17	Correct	4 ms	752 KB	Output is correct
18	Correct	4 ms	752 KB	Output is correct
19	Correct	14 ms	1256 KB	Output is correct
20	Correct	19 ms	1280 KB	Output is correct
21	Correct	15 ms	1280 KB	Output is correct
22	Correct	216 ms	1340 KB	Output is correct
23	Correct	270 ms	1416 KB	Output is correct
24	Correct	208 ms	1416 KB	Output is correct
25	Correct	178 ms	1420 KB	Output is correct
26	Correct	161 ms	1420 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	928 ms	35612 KB	Output is correct
2	Correct	871 ms	35660 KB	Output is correct
3	Correct	808 ms	35660 KB	Output is correct
4	Correct	746 ms	35660 KB	Output is correct
5	Correct	622 ms	35660 KB	Output is correct
6	Correct	692 ms	40116 KB	Output is correct
7	Correct	720 ms	44928 KB	Output is correct
8	Correct	708 ms	49644 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	49644 KB	Output is correct
2	Incorrect	267 ms	49644 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	759 ms	49644 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	3 ms	432 KB	Output is correct
4	Correct	2 ms	480 KB	Output is correct
5	Correct	2 ms	556 KB	Output is correct
6	Correct	3 ms	712 KB	Output is correct
7	Correct	2 ms	712 KB	Output is correct
8	Correct	3 ms	712 KB	Output is correct
9	Correct	3 ms	712 KB	Output is correct
10	Correct	2 ms	712 KB	Output is correct
11	Correct	2 ms	712 KB	Output is correct
12	Correct	3 ms	712 KB	Output is correct
13	Correct	3 ms	712 KB	Output is correct
14	Correct	3 ms	712 KB	Output is correct
15	Correct	2 ms	752 KB	Output is correct
16	Correct	5 ms	752 KB	Output is correct
17	Correct	4 ms	752 KB	Output is correct
18	Correct	4 ms	752 KB	Output is correct
19	Correct	14 ms	1256 KB	Output is correct
20	Correct	19 ms	1280 KB	Output is correct
21	Correct	15 ms	1280 KB	Output is correct
22	Correct	216 ms	1340 KB	Output is correct
23	Correct	270 ms	1416 KB	Output is correct
24	Correct	208 ms	1416 KB	Output is correct
25	Correct	178 ms	1420 KB	Output is correct
26	Correct	161 ms	1420 KB	Output is correct
27	Correct	40 ms	49644 KB	Output is correct
28	Correct	38 ms	49644 KB	Output is correct
29	Correct	30 ms	49644 KB	Output is correct
30	Correct	705 ms	49644 KB	Output is correct
31	Correct	724 ms	49644 KB	Output is correct
32	Correct	688 ms	49644 KB	Output is correct
33	Correct	299 ms	49644 KB	Output is correct
34	Correct	275 ms	49644 KB	Output is correct
35	Incorrect	271 ms	49644 KB	Output isn't correct
36	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	3 ms	432 KB	Output is correct
4	Correct	2 ms	480 KB	Output is correct
5	Correct	2 ms	556 KB	Output is correct
6	Correct	3 ms	712 KB	Output is correct
7	Correct	2 ms	712 KB	Output is correct
8	Correct	3 ms	712 KB	Output is correct
9	Correct	3 ms	712 KB	Output is correct
10	Correct	2 ms	712 KB	Output is correct
11	Correct	2 ms	712 KB	Output is correct
12	Correct	3 ms	712 KB	Output is correct
13	Correct	3 ms	712 KB	Output is correct
14	Correct	3 ms	712 KB	Output is correct
15	Correct	2 ms	752 KB	Output is correct
16	Correct	5 ms	752 KB	Output is correct
17	Correct	4 ms	752 KB	Output is correct
18	Correct	4 ms	752 KB	Output is correct
19	Correct	14 ms	1256 KB	Output is correct
20	Correct	19 ms	1280 KB	Output is correct
21	Correct	15 ms	1280 KB	Output is correct
22	Correct	216 ms	1340 KB	Output is correct
23	Correct	270 ms	1416 KB	Output is correct
24	Correct	208 ms	1416 KB	Output is correct
25	Correct	178 ms	1420 KB	Output is correct
26	Correct	161 ms	1420 KB	Output is correct
27	Correct	928 ms	35612 KB	Output is correct
28	Correct	871 ms	35660 KB	Output is correct
29	Correct	808 ms	35660 KB	Output is correct
30	Correct	746 ms	35660 KB	Output is correct
31	Correct	622 ms	35660 KB	Output is correct
32	Correct	692 ms	40116 KB	Output is correct
33	Correct	720 ms	44928 KB	Output is correct
34	Correct	708 ms	49644 KB	Output is correct
35	Correct	4 ms	49644 KB	Output is correct
36	Incorrect	267 ms	49644 KB	Output isn't correct
37	Halted	0 ms	0 KB	-

답안 #59939

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 12.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
12.0 / 12.0

Subtask #3
0 / 15.0

Subtask #4
0 / 23.0

Subtask #5
0 / 30.0

Subtask #6
0 / 13.0