QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#604029#9427. Collect the Coinsucup-team5062WA 14ms4352kbC++201.6kb2024-10-01 22:15:142024-10-01 22:15:16

Judging History

你现在查看的是最新测评结果

  • [2024-11-06 15:56:27]
  • hack成功,自动添加数据
  • (/hack/1139)
  • [2024-10-01 22:15:16]
  • 评测
  • 测评结果:WA
  • 用时:14ms
  • 内存:4352kb
  • [2024-10-01 22:15:14]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

bool Check(int N, vector<long long> &T, vector<long long> &C, long long V) {
	long long cl = 0;
	long long cr = (1LL << 30);

	// Simulation
	for (int i = 2; i <= N; i++) {
		bool flag = false;
		if (cl - V * T[i] <= C[i] && C[i] <= cr + V * T[i]) {
			flag = true;
		}

		// Second Choice
		if (T[i] - T[i - 1] == 0 || V * (T[i] - T[i - 1]) < abs(C[i] - C[i - 1])) {
			cl = 1LL * C[i - 1] + 1LL * V * T[i - 1];
			cr = 1LL * C[i - 1] - 1LL * V * T[i - 1];
			if (flag == false) return false;
		}
		if (flag == true) {
			cl = min(cl, 1LL * C[i] + 1LL * V * T[i]);
			cr = max(cr, 1LL * C[i] - 1LL * V * T[i]);
		}
	}
	return true;
}

int Solve(int N, vector<long long> T, vector<long long> C) {
	vector<pair<long long, long long>> Sorted;
	for (int i = 1; i <= N; i++) Sorted.push_back(make_pair(T[i], C[i]));
	sort(Sorted.begin(), Sorted.end());
	for (int i = 1; i <= N; i++) T[i] = Sorted[i - 1].first;
	for (int i = 1; i <= N; i++) C[i] = Sorted[i - 1].second;

	// Binary Search
	int cl = 0, cr = (1 << 30), cm, minx = (1 << 30);
	for (int i = 0; i < 35; i++) {
		cm = (cl + cr) / 2;
		bool ret = Check(N, T, C, cm);
		if (ret == true) { minx = min(minx, cm); cr = cm; }
		else { cl = cm; }
	}
	return (minx == (1 << 30) ? -1 : minx);
}

int main() {
	int T; scanf("%d", &T);
	for (int t = 1; t <= T; t++) {
		int N; scanf("%d", &N);
		vector<long long> T(N + 1, 0);
		vector<long long> C(N + 1, 0);
		for (int i = 1; i <= N; i++) scanf("%lld%lld", &T[i], &C[i]);
		printf("%d\n", Solve(N, T, C));
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3800kb

input:

3
5
1 1
3 7
3 4
4 3
5 10
1
10 100
3
10 100
10 1000
10 10000

output:

2
0
-1

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 14ms
memory: 4352kb

input:

1135
2
6 5
8 8
8
2 9
2 10
4 4
5 3
6 2
6 8
8 2
8 7
1
9 1
6
4 6
6 1
6 2
9 10
10 1
10 7
5
1 6
2 5
6 7
8 6
10 3
8
1 10
5 4
5 7
6 1
6 6
8 4
9 1
9 4
8
1 1
1 3
2 9
3 3
5 9
6 10
9 7
10 7
3
5 8
6 6
10 6
7
2 9
4 7
5 10
6 3
6 7
8 9
10 1
6
1 4
2 8
5 9
7 10
9 1
10 5
9
2 7
4 5
5 9
6 10
7 4
9 4
9 9
10 3
10 7
1
3 1...

output:

0
3
0
3
1
3
6
0
2
1
1
0
1
0
0
0
5
1
2
0
0
0
1
4
2
0
2
1
3
0
3
2
3
2
5
3
1
1
0
1
1
1
0
2
0
0
0
1
0
2
1
0
2
3
4
4
1
1
0
0
1
3
0
1
3
4
2
0
0
1
1
6
3
2
0
0
0
1
0
2
1
2
0
1
1
2
0
0
1
2
0
2
0
2
2
1
1
0
0
0
5
1
2
0
6
1
1
0
2
2
2
0
1
1
1
3
4
0
8
0
0
1
0
2
1
4
1
1
0
0
0
7
2
2
1
0
0
3
1
2
0
1
2
3
3
0
2
3
3
4
...

result:

wrong answer 9th lines differ - expected: '3', found: '2'