oj.uz

Submission #724233

# Submission time Handle Problem Language Result Execution time Memory
724233 2023-04-14T23:09:06 Z n0sk1ll Circle selection (APIO18_circle_selection) C++14
49 / 100
 3000 ms 658876 KB 
#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

map<pii,set<pair<pii,pii>>> koji;
int ans[300005];

int main()
{
    FAST;

    int R=2e9+1;

    set<pair<pii,pii>> krugovi;

    int n; cin>>n;
    ff(i,0,n)
    {
        int x,y,r; cin>>x>>y>>r;
        krugovi.insert({{r,-i},{x,y}});
        koji[{(x+1e9)/R,(y+1e9)/R}].insert({{r,-i},{x,y}});
    }

    while (!krugovi.empty())
    {
        auto it=*prev(krugovi.end());
        int r=it.xx.xx,i=-it.xx.yy,x=it.yy.xx,y=it.yy.yy;

        if (2*r<=R)
        {
            while (2*r<=R) R/=2;

            koji.clear();
            for (auto jt : krugovi)
            {
                int x1=jt.yy.xx,y1=jt.yy.yy;
                koji[{(x1+1e9)/R,(y1+1e9)/R}].insert(jt);
            }
        }


        vector<pair<pii,pii>> to_delete;

        fff(dx,-2,2) fff(dy,-2,2) for (auto jt : koji[{(x+1e9)/R+dx,(y+1e9)/R+dy}])
        {
            int r1=jt.xx.xx,i1=-jt.xx.yy,x1=jt.yy.xx,y1=jt.yy.yy;

            if ((li)(r+r1)*(r+r1) >= (li)(x-x1)*(x-x1) + (li)(y-y1)*(y-y1)) ans[i1]=i,to_delete.pb({{r1,-i1},{x1,y1}});
        }

        for (auto jt : to_delete)
        {
            krugovi.erase(jt);
            int x1=jt.yy.xx,y1=jt.yy.yy;
            koji[{(x1+1e9)/R,(y1+1e9)/R}].erase(jt);
        }
    }

    ff(i,0,n) cout<<ans[i]+1<<" ";
}

//Note to self: Check for overflow

/*

3
1 1 1
2 2 2
3 3 3

*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 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 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 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 2 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 5 ms 1212 KB Output is correct
20 Correct 6 ms 1112 KB Output is correct
21 Correct 6 ms 1108 KB Output is correct
22 Correct 34 ms 6340 KB Output is correct
23 Correct 35 ms 5728 KB Output is correct
24 Correct 35 ms 5252 KB Output is correct
25 Correct 34 ms 6192 KB Output is correct
26 Correct 37 ms 5692 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 706 ms 47412 KB Output is correct
2 Correct 717 ms 45664 KB Output is correct
3 Correct 698 ms 43416 KB Output is correct
4 Correct 720 ms 47316 KB Output is correct
5 Correct 950 ms 41516 KB Output is correct
6 Correct 1765 ms 86740 KB Output is correct
7 Correct 1100 ms 47080 KB Output is correct
8 Correct 1146 ms 51796 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1352 ms 98860 KB Output is correct
3 Execution timed out 3082 ms 320424 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 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 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 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 2 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 5 ms 1212 KB Output is correct
20 Correct 6 ms 1112 KB Output is correct
21 Correct 6 ms 1108 KB Output is correct
22 Correct 34 ms 6340 KB Output is correct
23 Correct 35 ms 5728 KB Output is correct
24 Correct 35 ms 5252 KB Output is correct
25 Correct 34 ms 6192 KB Output is correct
26 Correct 37 ms 5692 KB Output is correct
27 Correct 11 ms 2004 KB Output is correct
28 Correct 11 ms 1988 KB Output is correct
29 Correct 11 ms 2008 KB Output is correct
30 Correct 91 ms 12924 KB Output is correct
31 Correct 78 ms 11724 KB Output is correct
32 Correct 78 ms 10812 KB Output is correct
33 Correct 179 ms 17420 KB Output is correct
34 Correct 181 ms 17468 KB Output is correct
35 Correct 193 ms 15400 KB Output is correct
36 Correct 1269 ms 108372 KB Output is correct
37 Correct 1276 ms 94540 KB Output is correct
38 Correct 1320 ms 109836 KB Output is correct
39 Correct 1883 ms 33312 KB Output is correct
40 Correct 1911 ms 33352 KB Output is correct
41 Correct 1926 ms 33456 KB Output is correct
42 Correct 326 ms 20600 KB Output is correct
43 Correct 845 ms 188644 KB Output is correct
44 Correct 823 ms 189068 KB Output is correct
45 Correct 826 ms 188768 KB Output is correct
46 Correct 833 ms 189056 KB Output is correct
47 Correct 835 ms 189136 KB Output is correct
48 Correct 838 ms 189228 KB Output is correct
49 Correct 833 ms 189328 KB Output is correct
50 Correct 833 ms 189008 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 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 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 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 2 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 5 ms 1212 KB Output is correct
20 Correct 6 ms 1112 KB Output is correct
21 Correct 6 ms 1108 KB Output is correct
22 Correct 34 ms 6340 KB Output is correct
23 Correct 35 ms 5728 KB Output is correct
24 Correct 35 ms 5252 KB Output is correct
25 Correct 34 ms 6192 KB Output is correct
26 Correct 37 ms 5692 KB Output is correct
27 Correct 706 ms 47412 KB Output is correct
28 Correct 717 ms 45664 KB Output is correct
29 Correct 698 ms 43416 KB Output is correct
30 Correct 720 ms 47316 KB Output is correct
31 Correct 950 ms 41516 KB Output is correct
32 Correct 1765 ms 86740 KB Output is correct
33 Correct 1100 ms 47080 KB Output is correct
34 Correct 1146 ms 51796 KB Output is correct
35 Correct 0 ms 340 KB Output is correct
36 Correct 1352 ms 98860 KB Output is correct
37 Execution timed out 3082 ms 320424 KB Time limit exceeded
38 Halted 0 ms 0 KB -