oj.uz

Submission #51884

# Submission time Handle Problem Language Result Execution time Memory
51884 2018-06-22T11:22:35 Z Alexa2001 Circle selection (APIO18_circle_selection) C++17
0 / 100
 3000 ms 39844 KB 
#include <bits/stdc++.h>

/// 13:07

using namespace std;

typedef pair<int,int> Pair;
typedef long long ll;
const int Nmax = 3e5 + 5;

int n, i, id, R, lg;
int x[Nmax], y[Nmax], r[Nmax], ans[Nmax];
Pair ord[Nmax];
vector< vector<Pair> > v;
vector<int> start;

void rescale()
{
    int i;
    vector< vector<Pair> > nv;
    vector<Pair> q[2];

    for(auto w : v)
    {
        for(i=0; i<2; ++i) q[i].clear();

        for(auto val : w)
            if(!ans[val.second])
                q[(x[val.second] >> lg) & 1].push_back(val);

        for(i=0; i<2; ++i)
            if(q[i].size())
                nv.push_back(q[i]);
    }

    v = nv;
    start.resize(v.size());
    for(i=0; i<v.size(); ++i)
        start[i] = x[v[i][0].second];
}

inline ll sq(int x) { return (ll)x*x; }

inline bool intersect(int i, int j)
{
    return sq(x[i] - x[j]) + sq(y[i] - y[j]) <= sq(r[i] + r[j]);
}

int bs(int val)
{
    int pos = 0, bit = 0;
    for(; (1<<bit) < start.size(); ++bit);

    for(--bit; bit>=0; --bit)
        if(pos + (1<<bit) < start.size() && start[pos + (1<<bit)] < val)
            pos += (1<<bit);
    if(!pos) return start[0] < val;
}

void update_ans(int id)
{
    int pos, now, ly, ry, lx, rx;
    vector<Pair> :: iterator it;

  //  cout << "Writing step\n";
  //  cerr << v.size() << '\n';
    for(auto w : v)
    {
  //      cerr << "Another w:\n";
     //   for(auto val : w) cerr << val.first << ' ' << val.second << '\n';
    }

    lx = x[id] - 2 * r[id];
    rx = x[id] + 2 * r[id];

    ly = y[id] - 2 * r[id];
    ry = y[id] + 2 * r[id];

    for(pos = bs(lx); pos < start.size() && start[pos] <= rx; ++pos)
    {
        for(it = upper_bound(v[pos].begin(), v[pos].end(), make_pair(ly, 0) ); it != v[pos].end() && it->first <= ry; ++it)
        {
            now = it->second;
            if(!ans[now] && intersect(id, now))
                    ans[now] = id;
        }
    }
}

int main()
{
  //  freopen("input", "r", stdin);
  //  freopen("output", "w", stdout);

    cin.sync_with_stdio(false);

    int mnX = INT_MAX, mnY = INT_MAX;

    cin >> n;
    v.push_back({});
    for(i=1; i<=n; ++i)
    {
        cin >> x[i] >> y[i] >> r[i];
        ord[i] = {r[i], i};

        mnX = min(mnX, x[i]);
        mnY = min(mnY, y[i]);
    }

    for(i=1; i<=n; ++i)
    {
        x[i] -= mnX, y[i] -= mnY;
        v[0].push_back( {y[i], i} );
    }

    lg = 31;

    sort(v[0].begin(), v[0].end());
    sort(ord+1, ord+n+1,
         [&] (const Pair &a, const Pair &b) { if(a.first == b.first) return a.second < b.second; return a.first > b.first;} );

    for(i=1; i<=n; ++i)
    {
        id = ord[i].second;
        if(ans[id]) continue;

        while(lg && (1<<(lg-1)) >= r[id])
        {
            --lg;
            rescale();
        }

        update_ans(id);
    }

    for(i=1; i<=n; ++i) cout << ans[i] << ' ';
    return 0;
}

Compilation message

circle_selection.cpp: In function 'void rescale()':
circle_selection.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<v.size(); ++i)
              ~^~~~~~~~~
circle_selection.cpp: In function 'int bs(int)':
circle_selection.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(; (1<<bit) < start.size(); ++bit);
           ~~~~~~~~~^~~~~~~~~~~~~~
circle_selection.cpp:55:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(pos + (1<<bit) < start.size() && start[pos + (1<<bit)] < val)
            ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
circle_selection.cpp: In function 'void update_ans(int)':
circle_selection.cpp:79:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(pos = bs(lx); pos < start.size() && start[pos] <= rx; ++pos)
                       ~~~~^~~~~~~~~~~~~~
circle_selection.cpp: In function 'int bs(int)':
circle_selection.cpp:58:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 436 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Correct 2 ms 568 KB Output is correct
8 Incorrect 2 ms 572 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 24952 KB Output is correct
2 Incorrect 226 ms 33452 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 33452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 436 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Correct 2 ms 568 KB Output is correct
8 Incorrect 2 ms 572 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 436 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Correct 2 ms 568 KB Output is correct
8 Incorrect 2 ms 572 KB Output isn't correct
9 Halted 0 ms 0 KB -