oj.uz

Submission #60225

# Submission time Handle Problem Language Result Execution time Memory
60225 2018-07-23T21:56:38 Z duality Circle selection (APIO18_circle_selection) C++11
19 / 100
 3000 ms 37716 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long int LLI;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;

LLI sq(LLI n) { return n*n; }
struct circle { int x,y,r,i; };
bool comp(circle a,circle b) {
    if (a.r == b.r) return a.i < b.i;
    else return a.r > b.r;
}
circle c[300000];
int ans[300000];
pii sorted[300000];
int arr1[300000],arr2[300000];
int tree1[1 << 20],tree2[1 << 20];
int comp1(int a,int b) {
    if (a == -1) return b;
    else if (b == -1) return a;
    else if (arr1[a] > arr1[b]) return a;
    else return b;
}
int comp2(int a,int b) {
    if (a == -1) return b;
    else if (b == -1) return a;
    else if (arr2[a] > arr2[b]) return a;
    else return b;
}
int build1(int s,int e,int i) {
    if (s == e) {
        tree1[i] = s;
        return 0;
    }

    int mid = (s+e) / 2;
    build1(s,mid,2*i+1),build1(mid+1,e,2*i+2);
    tree1[i] = comp1(tree1[2*i+1],tree1[2*i+2]);
    return 0;
}
int query1(int s,int e,int qs,int qe,int i) {
    if ((s > qe) || (e < qs)) return -1;
    else if ((s >= qs) && (e <= qe)) return tree1[i];

    int mid = (s+e) / 2;
    return comp1(query1(s,mid,qs,qe,2*i+1),query1(mid+1,e,qs,qe,2*i+2));
}
int update1(int s,int e,int ai,int i) {
    if ((s > ai) || (e < ai)) return tree1[i];
    else if (s == e) return tree1[i];

    int mid = (s+e) / 2;
    tree1[i] = comp1(update1(s,mid,ai,2*i+1),update1(mid+1,e,ai,2*i+2));
    return tree1[i];
}
int build2(int s,int e,int i) {
    if (s == e) {
        tree2[i] = s;
        return 0;
    }

    int mid = (s+e) / 2;
    build2(s,mid,2*i+1),build2(mid+1,e,2*i+2);
    tree2[i] = comp2(tree2[2*i+1],tree2[2*i+2]);
    return 0;
}
int query2(int s,int e,int qs,int qe,int i) {
    if ((s > qe) || (e < qs)) return -1;
    else if ((s >= qs) && (e <= qe)) return tree2[i];

    int mid = (s+e) / 2;
    return comp2(query2(s,mid,qs,qe,2*i+1),query2(mid+1,e,qs,qe,2*i+2));
}
int update2(int s,int e,int ai,int i) {
    if ((s > ai) || (e < ai)) return tree2[i];
    else if (s == e) return tree2[i];

    int mid = (s+e) / 2;
    tree2[i] = comp2(update2(s,mid,ai,2*i+1),update2(mid+1,e,ai,2*i+2));
    return tree2[i];
}
int main() {
    int i;
    int n;
    int sub2 = 1;
    scanf("%d",&n);
    for (i = 0; i < n; i++) scanf("%d %d %d",&c[i].x,&c[i].y,&c[i].r),c[i].i = i,sub2 &= (c[i].y == 0);
    sort(c,c+n,comp);

    int j;
    if (sub2) {
        fill(ans,ans+n,-1);
        for (i = 0; i < n; i++) sorted[i] = mp(c[i].x,c[i].i);
        sort(sorted,sorted+n);
        for (i = 0; i < n; i++) {
            int p = lower_bound(sorted,sorted+n,mp(c[i].x,c[i].i))-sorted;
            arr1[p] = c[i].x+c[i].r,arr2[p] = c[i].r-c[i].x;
        }
        build1(0,n-1,0),build2(0,n-1,0);
        //for (i=0;i<7;i++)cout<<tree1[i];
        //for (i=0;i<7;i++)cout<<tree2[i];
        //cout<<endl;
        fill(ans,ans+n,-1);
        for (i = 0; i < n; i++) {
            if (ans[c[i].i] == -1) {
                while (1) {
                    int p = upper_bound(sorted,sorted+n,mp(c[i].x,n))-sorted-1;
                    //cout<<"p: "<<p<<endl;
                    p = query1(0,n-1,0,p,0);
                    if (arr1[p] >= c[i].x-c[i].r) {
                        arr1[p] = -2e9;
                        if (ans[sorted[p].second] == -1) ans[sorted[p].second] = c[i].i;
                        update1(0,n-1,p,0);
                    }
                    else {
                        p = lower_bound(sorted,sorted+n,mp(c[i].x,0))-sorted;
                        p = query2(0,n-1,p,n-1,0);
                        if (arr2[p] >= -(c[i].x+c[i].r)) {
                            arr2[p] = -2e9;
                            if (ans[sorted[p].second] == -1) ans[sorted[p].second] = c[i].i;
                            update2(0,n-1,p,0);
                        }
                        else break;
                    }
                }
                //for (j=0;j<7;j++)cout<<tree1[j];
                //cout<<endl;
        //for (j=0;j<7;j++)cout<<tree2[j];
        //cout<<endl;
            }
        }
    }
    else {
        fill(ans,ans+n,-1);
        for (i = 0; i < n; i++) {
            if (ans[c[i].i] == -1) {
                for (j = 0; j < n; j++) {
                    if (ans[c[j].i] == -1) {
                        if (sq(c[i].x-c[j].x)+sq(c[i].y-c[j].y) <= sq(c[i].r+c[j].r)) ans[c[j].i] = c[i].i;
                    }
                }
            }
        }
    }
    for (i = 0; i < n; i++) printf("%d ",ans[i]+1);

    return 0;
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
circle_selection.cpp:90:81: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < n; i++) scanf("%d %d %d",&c[i].x,&c[i].y,&c[i].r),c[i].i = i,sub2 &= (c[i].y == 0);
                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 3 ms 620 KB Output is correct
7 Correct 3 ms 624 KB Output is correct
8 Correct 3 ms 624 KB Output is correct
9 Correct 3 ms 624 KB Output is correct
10 Correct 2 ms 624 KB Output is correct
11 Correct 2 ms 624 KB Output is correct
12 Correct 2 ms 624 KB Output is correct
13 Correct 2 ms 624 KB Output is correct
14 Correct 3 ms 624 KB Output is correct
15 Correct 2 ms 624 KB Output is correct
16 Correct 4 ms 624 KB Output is correct
17 Correct 4 ms 624 KB Output is correct
18 Correct 4 ms 692 KB Output is correct
19 Correct 7 ms 748 KB Output is correct
20 Correct 8 ms 748 KB Output is correct
21 Correct 8 ms 764 KB Output is correct
22 Correct 61 ms 780 KB Output is correct
23 Correct 54 ms 780 KB Output is correct
24 Correct 56 ms 812 KB Output is correct
25 Correct 52 ms 812 KB Output is correct
26 Correct 56 ms 812 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 951 ms 21664 KB Output is correct
2 Correct 869 ms 23828 KB Output is correct
3 Correct 869 ms 23828 KB Output is correct
4 Correct 1026 ms 23828 KB Output is correct
5 Correct 691 ms 23828 KB Output is correct
6 Correct 1137 ms 28332 KB Output is correct
7 Correct 652 ms 33084 KB Output is correct
8 Correct 642 ms 37716 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 37716 KB Output is correct
2 Execution timed out 3028 ms 37716 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3021 ms 37716 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 3 ms 620 KB Output is correct
7 Correct 3 ms 624 KB Output is correct
8 Correct 3 ms 624 KB Output is correct
9 Correct 3 ms 624 KB Output is correct
10 Correct 2 ms 624 KB Output is correct
11 Correct 2 ms 624 KB Output is correct
12 Correct 2 ms 624 KB Output is correct
13 Correct 2 ms 624 KB Output is correct
14 Correct 3 ms 624 KB Output is correct
15 Correct 2 ms 624 KB Output is correct
16 Correct 4 ms 624 KB Output is correct
17 Correct 4 ms 624 KB Output is correct
18 Correct 4 ms 692 KB Output is correct
19 Correct 7 ms 748 KB Output is correct
20 Correct 8 ms 748 KB Output is correct
21 Correct 8 ms 764 KB Output is correct
22 Correct 61 ms 780 KB Output is correct
23 Correct 54 ms 780 KB Output is correct
24 Correct 56 ms 812 KB Output is correct
25 Correct 52 ms 812 KB Output is correct
26 Correct 56 ms 812 KB Output is correct
27 Correct 10 ms 37716 KB Output is correct
28 Correct 14 ms 37716 KB Output is correct
29 Correct 11 ms 37716 KB Output is correct
30 Correct 206 ms 37716 KB Output is correct
31 Correct 247 ms 37716 KB Output is correct
32 Correct 237 ms 37716 KB Output is correct
33 Correct 79 ms 37716 KB Output is correct
34 Correct 125 ms 37716 KB Output is correct
35 Correct 118 ms 37716 KB Output is correct
36 Execution timed out 3031 ms 37716 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 3 ms 620 KB Output is correct
7 Correct 3 ms 624 KB Output is correct
8 Correct 3 ms 624 KB Output is correct
9 Correct 3 ms 624 KB Output is correct
10 Correct 2 ms 624 KB Output is correct
11 Correct 2 ms 624 KB Output is correct
12 Correct 2 ms 624 KB Output is correct
13 Correct 2 ms 624 KB Output is correct
14 Correct 3 ms 624 KB Output is correct
15 Correct 2 ms 624 KB Output is correct
16 Correct 4 ms 624 KB Output is correct
17 Correct 4 ms 624 KB Output is correct
18 Correct 4 ms 692 KB Output is correct
19 Correct 7 ms 748 KB Output is correct
20 Correct 8 ms 748 KB Output is correct
21 Correct 8 ms 764 KB Output is correct
22 Correct 61 ms 780 KB Output is correct
23 Correct 54 ms 780 KB Output is correct
24 Correct 56 ms 812 KB Output is correct
25 Correct 52 ms 812 KB Output is correct
26 Correct 56 ms 812 KB Output is correct
27 Correct 951 ms 21664 KB Output is correct
28 Correct 869 ms 23828 KB Output is correct
29 Correct 869 ms 23828 KB Output is correct
30 Correct 1026 ms 23828 KB Output is correct
31 Correct 691 ms 23828 KB Output is correct
32 Correct 1137 ms 28332 KB Output is correct
33 Correct 652 ms 33084 KB Output is correct
34 Correct 642 ms 37716 KB Output is correct
35 Correct 2 ms 37716 KB Output is correct
36 Execution timed out 3028 ms 37716 KB Time limit exceeded
37 Halted 0 ms 0 KB -