oj.uz

Submission #831945

# Submission time Handle Problem Language Result Execution time Memory
831945 2023-08-20T18:24:22 Z DarkMatter Lightning Rod (NOI18_lightningrod) C++14
23 / 100
 1529 ms 262144 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int>pi;
typedef pair<ll, ll>pl;
typedef vector<pi>vpi;
typedef vector<pl>vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<bool> vb;
const long double PI = acos(-1);
const ll oo = 1e18;
const int MOD = 1e9 + 7;
const int N = 2e5 + 7;
#define endl '\n'
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define read(v) for (auto& it : v) scanf("%d", &it);
#define readL(v) for (auto& it : v) scanf("%lld", &it);
#define print(v) for (auto it : v) printf("%d ", it); puts("");
#define printL(v) for (auto it : v) printf("%lld ", it); puts("");
ll n;
vpl v;
ll ans = oo;
void calc(ll idx, vpl cur) {
	if (idx == n) {
		vb vis(n, false);
		for (int i = 0; i < cur.size(); i++) {
			for (int j = 0; j < n; j++) {
				if (vis[j])
					continue;
				if (abs(cur[i].first - v[j].first) <= (cur[i].second - v[j].second))
					vis[j] = true;
			}
		}
		sort(all(vis));
		if (vis[0])
			ans = min(ans, (ll)cur.size());
		return;
	}
	calc(idx + 1, cur);
	cur.push_back(v[idx]);
	calc(idx + 1, cur);
}
void solve() {
	scanf("%lld", &n);
	v.resize(n);
	ans = oo;
	bool ok = true;
	for (auto& it : v) {
		scanf("%lld %lld", &it.first, &it.second);
		if (it.second != 1)
			ok = false;
	}
	if (ok) {
		cout << n << endl;
		return;
	}
	if (n <= 20) {
		vpl cur;
		calc(0, cur);
		printf("%lld\n", ans);
		return;
	}
	vpl newV;
	for (auto& it : v)
		newV.push_back({ it.second,it.first });
	sort(all(newV), greater<pl>());
	v = newV;
	ans = 0;
	for (int i = 0; i < n; i++) {
		bool ok = true;
		for (int j = 0; j < i; j++)
			ok &= (abs(v[i].second - v[j].second) > (v[i].first - v[j].first));
		ans += ok;
	}
	printf("%lld\n", ans);
}
int t = 1;
int main() {
	//#ifndef ONLINE_JUDGE
	//	freopen("input.txt", "r", stdin);
	//#endif
		//scanf("%d", &t);
	while (t--) solve();
}

Compilation message

lightningrod.cpp: In function 'void calc(ll, vpl)':
lightningrod.cpp:34:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for (int i = 0; i < cur.size(); i++) {
      |                   ~~^~~~~~~~~~~~
lightningrod.cpp: In function 'void solve()':
lightningrod.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  scanf("%lld", &n);
      |  ~~~~~^~~~~~~~~~~~
lightningrod.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%lld %lld", &it.first, &it.second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1428 ms 152140 KB Output is correct
2 Correct 1431 ms 151580 KB Output is correct
3 Correct 1366 ms 147500 KB Output is correct

Subtask #2
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 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #3
12.0 / 12.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 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 321 ms 296 KB Output is correct
9 Correct 700 ms 308 KB Output is correct
10 Correct 748 ms 312 KB Output is correct

Subtask #4
0 / 21.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 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 321 ms 296 KB Output is correct
9 Correct 700 ms 308 KB Output is correct
10 Correct 748 ms 312 KB Output is correct
11 Incorrect 3 ms 340 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 26.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 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 321 ms 296 KB Output is correct
9 Correct 700 ms 308 KB Output is correct
10 Correct 748 ms 312 KB Output is correct
11 Incorrect 3 ms 340 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1529 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1428 ms 152140 KB Output is correct
2 Correct 1431 ms 151580 KB Output is correct
3 Correct 1366 ms 147500 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 321 ms 296 KB Output is correct
12 Correct 700 ms 308 KB Output is correct
13 Correct 748 ms 312 KB Output is correct
14 Incorrect 3 ms 340 KB Output isn't correct
15 Halted 0 ms 0 KB -