oj.uz

Submission #103866

# Submission time Handle Problem Language Result Execution time Memory
103866 2019-04-03T04:05:05 Z dupreez Circle selection (APIO18_circle_selection) C++14
12 / 100
 2149 ms 50280 KB 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <cstdio>
#include <cmath>
#include <bitset>
#define mk make_pair
#define pb push_back
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pos;

const ll MOD = 1000000007, N =300010, dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 }, MIN = -7230040172838, MAX = 7230040172838;
const int S = 60;
ll mn(ll a, ll b) {
	if (a == -1)return b;
	if (b == -1)return a;
	return min(a, b);
}
static ll gcd(ll v1, ll v2) {
	if (v1 == 0)return v2; if (v2 == 0)return v1; if (v2 > v1)return gcd(v2%v1, v1); return gcd(v1%v2, v2);
}

ll pw(ll v1, ll v2) {
	ll v3 = 1;
	while (v2 > 0) {
		if (v2 % 2)v3 = (v3*v1) % MOD;
		v1 = (v1*v1) % MOD;
		v2 /= 2;
	}
	return v3;
}

int n, as[N], xv[N], rgl[N*2];
pos x[N], r[N];
set<pos> rg;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int v1;
		cin >> xv[i] >> v1 >> r[i].first;
		r[i].second = -i;
		rg.insert(mk(xv[i] - r[i].first, i));
		rg.insert(mk(xv[i] + r[i].first, i));
		if (v1 != 0)return 0;
	}

	sort(r + 1, r + n + 1);
	memset(as, -1, sizeof(as));
	for (int i = n; i >= 1; i--) {
		int ci = -r[i].second;
		if (as[ci] != -1)continue;
		int lb = xv[ci] - r[i].first, ub = xv[ci] + r[i].first;
		for (auto i1 = rg.lower_bound(mk(lb,-1)); i1!=rg.end()&&(*i1).first <= ub; i1 = rg.lower_bound(mk(lb, -1))) {
			int ni = (*i1).second;
			if (as[ni] == -1)as[ni] = ci;
			rg.erase(i1);
		}
	}
	for (int i = 1; i <= n; i++)cout << as[i] << endl;
	return 0;
}

Compilation message

circle_selection.cpp: In function 'll gcd(ll, ll)':
circle_selection.cpp:27:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (v1 == 0)return v2; if (v2 == 0)return v1; if (v2 > v1)return gcd(v2%v1, v1); return gcd(v1%v2, v2);
  ^~
circle_selection.cpp:27:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if (v1 == 0)return v2; if (v2 == 0)return v1; if (v2 > v1)return gcd(v2%v1, v1); return gcd(v1%v2, v2);
                         ^~

Subtask #1
0 / 7.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2149 ms 50280 KB Output is correct
2 Correct 1850 ms 50216 KB Output is correct
3 Correct 1967 ms 49996 KB Output is correct
4 Correct 2031 ms 50176 KB Output is correct
5 Correct 1762 ms 50104 KB Output is correct
6 Correct 1741 ms 50232 KB Output is correct
7 Correct 1792 ms 49988 KB Output is correct
8 Correct 1686 ms 50044 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

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

Subtask #6
0 / 13.0

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