QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#102733#3194. Knapsack CollectionPetroTarnavskyi#WA 136ms81468kbC++171.3kb2023-05-03 16:44:062023-05-03 16:44:10

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-03 16:44:10]
  • 评测
  • 测评结果:WA
  • 用时:136ms
  • 内存:81468kb
  • [2023-05-03 16:44:06]
  • 提交

answer

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

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

const int MX = 1e7 + 47;
LL ans[MX];
int n, s, t;

void f(int i, multiset<int> m)
{
	if (ans[i]) return;
	while (!m.empty())
	{
		int pos = (i + ans[i]) % s;
		auto it = m.lower_bound(pos);
		if (it == m.end()) it = m.begin();
		int pos2 = *it;
		m.erase(it);
		ans[i] += (pos2 - pos + s) % s;
		ans[i] += t;		
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> s >> t;
	
	multiset<int> ms;
	FOR(i, 0, n)
	{
		int a;
		cin >> a;
		ms.insert(a);
	}
	for (auto i : ms) f(i, ms);
	int j = *ms.begin();
	int val = ans[j];
	FOR(i, 0, s)
	{
		int k = (j - i + s) % s;		
		if (ans[k]) val = ans[k];
		else ans[k] = ++val;
	}
	cout << *min_element(ans, ans + s) << '\n';
	cout << *max_element(ans, ans + s) << '\n';
	LL sum = accumulate(ans, ans + s, 0ll);
	LL g = gcd(sum, s);
	cout << sum / g << '/' << s / g << '\n';
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

7 10 10000000
0 0 0 0 0 0 1

output:

70000001
70000009
350000027/5

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 2ms
memory: 3368kb

input:

10 10 3
0 0 2 2 4 4 6 6 8 8

output:

39
40
79/2

result:

ok 3 lines

Test #3:

score: 0
Accepted
time: 70ms
memory: 81468kb

input:

9 10000000 1
0 7 2 3 4 5 6 1 8

output:

9
10000000
12500021249991/2500000

result:

ok 3 lines

Test #4:

score: -100
Wrong Answer
time: 136ms
memory: 48356kb

input:

1000 5752352 9302172
1473740 1253927 2058266 2440001 3007902 2154122 5162393 1447874 5636700 2726828 3029551 3245083 3959896 1675726 5612527 5425457 2603081 959614 619276 579327 1512143 3107246 4323157 2224868 491514 4037564 5737062 1155534 4260273 1099943 3864642 4100143 2282326 3273233 3346948 250...

output:

893486527
9489162722
1291202822513755/1438088

result:

wrong answer 1st lines differ - expected: '9483421118', found: '893486527'