oj.uz

Submission #831943

# Submission time Handle Problem Language Result Execution time Memory
831943 2023-08-20T18:19:53 Z DarkMatter Lightning Rod (NOI18_lightningrod) C++14
23 / 100
 2000 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;
	}
	vpl cur;
	calc(0, cur);
	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 1433 ms 152040 KB Output is correct
2 Correct 1637 ms 151576 KB Output is correct
3 Correct 1503 ms 147504 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 1 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 1 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 397 ms 300 KB Output is correct
9 Correct 905 ms 308 KB Output is correct
10 Correct 856 ms 296 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 1 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 397 ms 300 KB Output is correct
9 Correct 905 ms 308 KB Output is correct
10 Correct 856 ms 296 KB Output is correct
11 Execution timed out 2062 ms 724 KB Time limit exceeded
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 1 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 397 ms 300 KB Output is correct
9 Correct 905 ms 308 KB Output is correct
10 Correct 856 ms 296 KB Output is correct
11 Execution timed out 2062 ms 724 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1501 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 1433 ms 152040 KB Output is correct
2 Correct 1637 ms 151576 KB Output is correct
3 Correct 1503 ms 147504 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 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 397 ms 300 KB Output is correct
12 Correct 905 ms 308 KB Output is correct
13 Correct 856 ms 296 KB Output is correct
14 Execution timed out 2062 ms 724 KB Time limit exceeded
15 Halted 0 ms 0 KB -