oj.uz

Submission #107292

# Submission time Handle Problem Language Result Execution time Memory
107292 2019-04-23T06:57:24 Z leduykhongngu Circle selection (APIO18_circle_selection) C++11
72 / 100
 3000 ms 66532 KB 
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a),_b=(b); i<=_b; ++i)
#define FORR(i,a,b) for (int i=(a),_b=(b); i>=_b; --i)
#define REP(i,b) for (int i=0,_b=(b); i<_b; ++i)
#define endl '\n'
#define sz(x) (int) x.size()
#define mod %
#define fillchar(x,y,z) memset(x,z,y)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
typedef long long int64;
typedef unsigned long long qword;
using namespace std;
const int maxn=3e5+5;
inline int64 sqr(int64 x)
{
    return x*x;
}
struct Circle{
    int64 x,y,r;
    int id;

    bool IsIntersect(const Circle &c)
    {
        return sqr(x-c.x)+sqr(y-c.y)<=sqr(r+c.r);
    }
}cir[maxn];
bool operator <(const Circle &b,const Circle &c)
    {
        return mp(-b.r,b.id)<mp(-c.r,c.id);
    }
vector<set<pii> > Point;
vector<int> X;
int n;
int ans[maxn];
pii tmp[maxn];
int main()
{
    #ifdef meomeomeooooo
        freopen("input.txt","r",stdin);
        //freopen(".txt","w",stdout);
    #endif // meomeomeooooo
    iostream::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    set<Circle> myset;
    FOR(i,1,n) {
        cin >> cir[i].x >> cir[i].y >> cir[i].r;
        X.push_back(cir[i].x);
        cir[i].id=i;
        myset.insert(cir[i]);
    }
    sort(X.begin(),X.end());
    X.resize(unique(X.begin(),X.end())-X.begin());
    #define GetDec(x) (lower_bound(X.begin(),X.end(),x)-X.begin())
    Point.resize(X.size());
    FOR(i,1,n) {
        int x=GetDec(cir[i].x);
        Point[x].insert({cir[i].y,cir[i].id});
    }
    while (myset.size()) {
        Circle cur=*myset.begin(); myset.erase(cur);
        ans[cur.id]=cur.id;
        int x=cur.x,y=cur.y,r=cur.r;
        int Lx=max(1ll*x-2*r,-1000000000ll);
        int Rx=min(1ll*x+2*r,1000000000ll);
        int Ly=max(1ll*y-2*r,-1000000000ll);
        int Ry=min(1ll*y+2*r,1000000000ll);
        Lx=GetDec(Lx);
        for (int i=Lx; i<X.size()&&X[i]<=Rx; ++i) {
            int top=0;
            for (auto j=Point[i].lower_bound(mp(Ly,0)); j!=Point[i].end()&&(*j).fi<=Ry; ++j) {
                int id=(*j).se;
                if (cur.IsIntersect(cir[id])) {
                    assert(ans[id]==0||ans[id]==cur.id);
                    ans[id]=cur.id;
                    myset.erase(cir[id]);
                    tmp[++top]=*j;
                }
            }
            FOR(j,1,top)
                Point[i].erase(tmp[j]);
        }
    }
    FOR(i,1,n)
        cout << ans[i] << ' ';
    return 0;
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:72:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=Lx; i<X.size()&&X[i]<=Rx; ++i) {
                        ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 4 ms 640 KB Output is correct
17 Correct 4 ms 640 KB Output is correct
18 Correct 4 ms 640 KB Output is correct
19 Correct 11 ms 1536 KB Output is correct
20 Correct 11 ms 1536 KB Output is correct
21 Correct 13 ms 1792 KB Output is correct
22 Correct 11 ms 1536 KB Output is correct
23 Correct 16 ms 1536 KB Output is correct
24 Correct 14 ms 1536 KB Output is correct
25 Correct 8 ms 1536 KB Output is correct
26 Correct 10 ms 1536 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1245 ms 66356 KB Output is correct
2 Correct 1263 ms 66532 KB Output is correct
3 Correct 1225 ms 66280 KB Output is correct
4 Correct 1249 ms 66408 KB Output is correct
5 Correct 1000 ms 61668 KB Output is correct
6 Correct 1060 ms 66276 KB Output is correct
7 Correct 1043 ms 65696 KB Output is correct
8 Correct 1118 ms 66100 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 441 ms 22460 KB Output is correct
3 Correct 1529 ms 66504 KB Output is correct
4 Correct 1483 ms 66200 KB Output is correct
5 Correct 2147 ms 64320 KB Output is correct
6 Correct 761 ms 34816 KB Output is correct
7 Correct 309 ms 18748 KB Output is correct
8 Correct 40 ms 4472 KB Output is correct
9 Correct 1655 ms 66148 KB Output is correct
10 Execution timed out 3052 ms 64228 KB Time limit exceeded

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 893 ms 66404 KB Output is correct
2 Correct 611 ms 66160 KB Output is correct
3 Correct 2151 ms 65828 KB Output is correct
4 Correct 620 ms 66212 KB Output is correct
5 Correct 619 ms 66148 KB Output is correct
6 Correct 2234 ms 65536 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 4 ms 640 KB Output is correct
17 Correct 4 ms 640 KB Output is correct
18 Correct 4 ms 640 KB Output is correct
19 Correct 11 ms 1536 KB Output is correct
20 Correct 11 ms 1536 KB Output is correct
21 Correct 13 ms 1792 KB Output is correct
22 Correct 11 ms 1536 KB Output is correct
23 Correct 16 ms 1536 KB Output is correct
24 Correct 14 ms 1536 KB Output is correct
25 Correct 8 ms 1536 KB Output is correct
26 Correct 10 ms 1536 KB Output is correct
27 Correct 25 ms 2820 KB Output is correct
28 Correct 20 ms 2808 KB Output is correct
29 Correct 24 ms 2916 KB Output is correct
30 Correct 29 ms 2816 KB Output is correct
31 Correct 28 ms 2780 KB Output is correct
32 Correct 26 ms 2816 KB Output is correct
33 Correct 328 ms 22432 KB Output is correct
34 Correct 328 ms 22384 KB Output is correct
35 Correct 351 ms 22384 KB Output is correct
36 Correct 320 ms 22356 KB Output is correct
37 Correct 339 ms 22484 KB Output is correct
38 Correct 331 ms 22356 KB Output is correct
39 Correct 1353 ms 17588 KB Output is correct
40 Correct 1350 ms 17764 KB Output is correct
41 Correct 1367 ms 17648 KB Output is correct
42 Correct 338 ms 17648 KB Output is correct
43 Correct 213 ms 22424 KB Output is correct
44 Correct 206 ms 22384 KB Output is correct
45 Correct 183 ms 22460 KB Output is correct
46 Correct 214 ms 22332 KB Output is correct
47 Correct 184 ms 22380 KB Output is correct
48 Correct 198 ms 22384 KB Output is correct
49 Correct 197 ms 22380 KB Output is correct
50 Correct 204 ms 22384 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 4 ms 640 KB Output is correct
17 Correct 4 ms 640 KB Output is correct
18 Correct 4 ms 640 KB Output is correct
19 Correct 11 ms 1536 KB Output is correct
20 Correct 11 ms 1536 KB Output is correct
21 Correct 13 ms 1792 KB Output is correct
22 Correct 11 ms 1536 KB Output is correct
23 Correct 16 ms 1536 KB Output is correct
24 Correct 14 ms 1536 KB Output is correct
25 Correct 8 ms 1536 KB Output is correct
26 Correct 10 ms 1536 KB Output is correct
27 Correct 1245 ms 66356 KB Output is correct
28 Correct 1263 ms 66532 KB Output is correct
29 Correct 1225 ms 66280 KB Output is correct
30 Correct 1249 ms 66408 KB Output is correct
31 Correct 1000 ms 61668 KB Output is correct
32 Correct 1060 ms 66276 KB Output is correct
33 Correct 1043 ms 65696 KB Output is correct
34 Correct 1118 ms 66100 KB Output is correct
35 Correct 2 ms 384 KB Output is correct
36 Correct 441 ms 22460 KB Output is correct
37 Correct 1529 ms 66504 KB Output is correct
38 Correct 1483 ms 66200 KB Output is correct
39 Correct 2147 ms 64320 KB Output is correct
40 Correct 761 ms 34816 KB Output is correct
41 Correct 309 ms 18748 KB Output is correct
42 Correct 40 ms 4472 KB Output is correct
43 Correct 1655 ms 66148 KB Output is correct
44 Execution timed out 3052 ms 64228 KB Time limit exceeded