oj.uz

Submission #107293

# Submission time Handle Problem Language Result Execution time Memory
107293 2019-04-23T07:01:58 Z leduykhongngu Circle selection (APIO18_circle_selection) C++11
72 / 100
 3000 ms 66124 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;
int ReadInt()
{
    char c;
    for (c = getchar(); c!='-'&&(c < '0' || c > '9'); c = getchar());
    int nega=0;
    int ans = c - '0';
    if (c=='-') nega=1,ans=0;
    for (c = getchar(); c >= '0' && c <= '9'; c = getchar())
        ans = ans * 10 + c - '0';
    if (nega) return -ans;
    return ans;
}
void WriteInt(int x)
{
    if (x > 9) WriteInt(x / 10);
    putchar(x % 10 + '0');
}
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);
    n=ReadInt();
    set<Circle> myset;
    FOR(i,1,n) {
        //cin >> cir[i].x >> cir[i].y >> cir[i].r;
        cir[i].x=ReadInt(); cir[i].y=ReadInt(); cir[i].r=ReadInt();
        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) {
        WriteInt(ans[i]); putchar(' ');
    }
    return 0;
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:90: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 3 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 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 4 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 5 ms 512 KB Output is correct
17 Correct 3 ms 640 KB Output is correct
18 Correct 4 ms 640 KB Output is correct
19 Correct 12 ms 1536 KB Output is correct
20 Correct 13 ms 1536 KB Output is correct
21 Correct 12 ms 1536 KB Output is correct
22 Correct 11 ms 1536 KB Output is correct
23 Correct 12 ms 1536 KB Output is correct
24 Correct 12 ms 1536 KB Output is correct
25 Correct 11 ms 1536 KB Output is correct
26 Correct 11 ms 1536 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1391 ms 65964 KB Output is correct
2 Correct 1394 ms 66068 KB Output is correct
3 Correct 1397 ms 65732 KB Output is correct
4 Correct 1382 ms 66124 KB Output is correct
5 Correct 1032 ms 61264 KB Output is correct
6 Correct 1050 ms 65688 KB Output is correct
7 Correct 1104 ms 64952 KB Output is correct
8 Correct 1094 ms 65452 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 356 ms 22208 KB Output is correct
3 Correct 1681 ms 65808 KB Output is correct
4 Correct 1474 ms 65776 KB Output is correct
5 Correct 2167 ms 64196 KB Output is correct
6 Correct 816 ms 34500 KB Output is correct
7 Correct 269 ms 18416 KB Output is correct
8 Correct 36 ms 4216 KB Output is correct
9 Correct 1833 ms 65856 KB Output is correct
10 Execution timed out 3016 ms 64008 KB Time limit exceeded

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 802 ms 66016 KB Output is correct
2 Correct 557 ms 65892 KB Output is correct
3 Correct 2206 ms 65636 KB Output is correct
4 Correct 614 ms 65936 KB Output is correct
5 Correct 587 ms 65996 KB Output is correct
6 Correct 2140 ms 65352 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 3 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 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 4 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 5 ms 512 KB Output is correct
17 Correct 3 ms 640 KB Output is correct
18 Correct 4 ms 640 KB Output is correct
19 Correct 12 ms 1536 KB Output is correct
20 Correct 13 ms 1536 KB Output is correct
21 Correct 12 ms 1536 KB Output is correct
22 Correct 11 ms 1536 KB Output is correct
23 Correct 12 ms 1536 KB Output is correct
24 Correct 12 ms 1536 KB Output is correct
25 Correct 11 ms 1536 KB Output is correct
26 Correct 11 ms 1536 KB Output is correct
27 Correct 15 ms 2688 KB Output is correct
28 Correct 22 ms 2680 KB Output is correct
29 Correct 19 ms 2688 KB Output is correct
30 Correct 18 ms 2688 KB Output is correct
31 Correct 19 ms 2688 KB Output is correct
32 Correct 17 ms 2688 KB Output is correct
33 Correct 341 ms 22384 KB Output is correct
34 Correct 336 ms 22252 KB Output is correct
35 Correct 350 ms 22256 KB Output is correct
36 Correct 331 ms 22256 KB Output is correct
37 Correct 312 ms 22256 KB Output is correct
38 Correct 331 ms 22384 KB Output is correct
39 Correct 1463 ms 17776 KB Output is correct
40 Correct 1258 ms 17648 KB Output is correct
41 Correct 1357 ms 17748 KB Output is correct
42 Correct 325 ms 17520 KB Output is correct
43 Correct 183 ms 22256 KB Output is correct
44 Correct 194 ms 22320 KB Output is correct
45 Correct 197 ms 22380 KB Output is correct
46 Correct 194 ms 22256 KB Output is correct
47 Correct 181 ms 22256 KB Output is correct
48 Correct 193 ms 22256 KB Output is correct
49 Correct 176 ms 22256 KB Output is correct
50 Correct 170 ms 22256 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 3 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 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 4 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 5 ms 512 KB Output is correct
17 Correct 3 ms 640 KB Output is correct
18 Correct 4 ms 640 KB Output is correct
19 Correct 12 ms 1536 KB Output is correct
20 Correct 13 ms 1536 KB Output is correct
21 Correct 12 ms 1536 KB Output is correct
22 Correct 11 ms 1536 KB Output is correct
23 Correct 12 ms 1536 KB Output is correct
24 Correct 12 ms 1536 KB Output is correct
25 Correct 11 ms 1536 KB Output is correct
26 Correct 11 ms 1536 KB Output is correct
27 Correct 1391 ms 65964 KB Output is correct
28 Correct 1394 ms 66068 KB Output is correct
29 Correct 1397 ms 65732 KB Output is correct
30 Correct 1382 ms 66124 KB Output is correct
31 Correct 1032 ms 61264 KB Output is correct
32 Correct 1050 ms 65688 KB Output is correct
33 Correct 1104 ms 64952 KB Output is correct
34 Correct 1094 ms 65452 KB Output is correct
35 Correct 2 ms 512 KB Output is correct
36 Correct 356 ms 22208 KB Output is correct
37 Correct 1681 ms 65808 KB Output is correct
38 Correct 1474 ms 65776 KB Output is correct
39 Correct 2167 ms 64196 KB Output is correct
40 Correct 816 ms 34500 KB Output is correct
41 Correct 269 ms 18416 KB Output is correct
42 Correct 36 ms 4216 KB Output is correct
43 Correct 1833 ms 65856 KB Output is correct
44 Execution timed out 3016 ms 64008 KB Time limit exceeded