QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#102746#3194. Knapsack CollectionPetroTarnavskyi#AC ✓568ms81756kbC++171.3kb2023-05-03 16:57:152023-05-03 16:57:17

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:57:17]
  • 评测
  • 测评结果:AC
  • 用时:568ms
  • 内存:81756kb
  • [2023-05-03 16:57:15]
  • 提交

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();
	LL 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: 3448kb

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: 3404kb

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: 80ms
memory: 81492kb

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: 0
Accepted
time: 154ms
memory: 48400kb

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:

9483421118
9489178267
13642137196405851/1438088

result:

ok 3 lines

Test #5:

score: 0
Accepted
time: 529ms
memory: 43992kb

input:

2000 5165496 4213116
1580125 1573107 287840 2532661 2096518 3429527 863764 2110386 1671454 5080610 4386787 3783675 1683589 87356 4316759 2782555 2521084 1203965 904795 2168957 3539129 2763986 114698 4040552 376611 3436138 577737 4502797 673049 1117185 3665448 441248 238260 2431152 5115231 2091879 70...

output:

8599593087
8604763955
4937170287749699/573944

result:

ok 3 lines

Test #6:

score: 0
Accepted
time: 568ms
memory: 68232kb

input:

2000 8269899 4441863
5687840 4674618 3561296 2135125 944352 527766 7980939 3413786 6079470 2386656 7600833 5025239 7844883 870382 4539039 1770583 2683639 3228848 3648708 5845638 3419462 4947794 6878580 2251424 2982582 2489034 1741387 6066819 2272462 5987270 4308094 71806 6285812 4098740 7127199 4364...

output:

9217102907
9225379247
76258758957286538/8269899

result:

ok 3 lines

Test #7:

score: 0
Accepted
time: 61ms
memory: 4380kb

input:

1000 123456 100000
36720 49646 54144 45445 50736 50446 46220 50300 36943 50702 41684 47453 38354 42431 35103 51158 46294 36211 46295 36827 52652 47155 36468 45804 38934 37743 44557 45114 53291 42170 51650 37199 36492 44639 40081 39028 40938 50294 43195 53460 44061 50265 39417 52934 52394 43163 42153...

output:

123432481
123555999
5082036259445/41152

result:

ok 3 lines

Test #8:

score: 0
Accepted
time: 246ms
memory: 4480kb

input:

2000 123456 100000
102375 101532 111049 99167 100970 109119 118163 109299 112321 101822 106053 108136 113267 112789 100214 107045 104640 105505 105442 108023 105785 103730 100019 104281 102214 115173 107442 118390 104379 115158 104147 111026 112254 103419 107075 115056 109505 115699 101783 101717 11...

output:

246888544
247011999
493900543/2

result:

ok 3 lines

Test #9:

score: 0
Accepted
time: 153ms
memory: 81756kb

input:

2000 9999999 10000000
3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 3521182 352118...

output:

39989996002
39999996000
39994996001/1

result:

ok 3 lines

Test #10:

score: 0
Accepted
time: 158ms
memory: 81684kb

input:

2000 9999997 10000000
1083611 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 1083610 108361...

output:

39989988005
39999988002
399949760055035987/9999997

result:

ok 3 lines

Test #11:

score: 0
Accepted
time: 479ms
memory: 77524kb

input:

2000 9458193 7026128
4968325 4379221 5909136 5032977 8253172 6454888 96313 8617319 4678737 8914912 3629642 1661551 4114997 4472796 3656034 2880755 4642176 3663959 875628 3935882 6144073 9174348 6754425 3535067 748171 4019095 872254 3812122 2157963 5293869 6738934 7313860 4433701 4356055 3685377 4455...

output:

16445365405
16454823754
155588170143608345/9458193

result:

ok 3 lines

Test #12:

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

input:

1 1 1
0

output:

1
1
1/1

result:

ok 3 lines

Test #13:

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

input:

5 1 1
0 0 0 0 0

output:

5
5
5/1

result:

ok 3 lines

Test #14:

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

input:

5 10 1
0 0 0 0 0

output:

41
50
91/2

result:

ok 3 lines

Test #15:

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

input:

1 10 3
7

output:

3
12
15/2

result:

ok 3 lines

Test #16:

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

input:

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

output:

10
10
10/1

result:

ok 3 lines

Test #17:

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

input:

3 9 3
2 5 8

output:

9
11
10/1

result:

ok 3 lines

Test #18:

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

input:

3 9 2
2 5 8

output:

8
10
9/1

result:

ok 3 lines

Test #19:

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

input:

3 9 4
2 5 8

output:

16
18
17/1

result:

ok 3 lines

Test #20:

score: 0
Accepted
time: 371ms
memory: 81736kb

input:

2000 9999999 3333337
4289563 1692945 1692945 1692945 6516708 1692945 1692945 1692945 5180676 4089202 5005214 4702596 1692945 8722889 1692945 1692945 5634153 9133205 1692945 8175073 1176342 1692945 4289563 4289563 9798329 9566525 2776132 1760147 1692945 2907094 1692945 9798329 5634153 5005214 8175073...

output:

7743332563
7753332561
7748332562/1

result:

ok 3 lines

Test #21:

score: 0
Accepted
time: 183ms
memory: 81644kb

input:

2000 9999999 7654321
4289563 4289563 4289563 4289563 4289563 4289563 4289563 4289563 4289563 4289563 4289563 4289563 4289563 8722889 4289563 4289563 4289563 4289563 4289563 8722889 4289563 4289563 4289563 4289563 4289563 9566525 8722889 1760147 4289563 2907094 4289563 4289563 4289563 4289563 8722889...

output:

18927652429
18937652427
18932652428/1

result:

ok 3 lines

Test #22:

score: 0
Accepted
time: 56ms
memory: 81528kb

input:

200 9999999 136137
4289563 4425699 4561836 4697971 4834109 4970244 5106380 5242517 5378656 5514792 5650929 5787066 5923201 6059340 6195478 6331614 6467749 6603885 6740022 6876158 7012294 7148432 7284569 7420708 7556845 7692980 7829117 7965255 8101392 8237527 8373666 8509803 8645940 8782078 8918217 9...

output:

37215256
40136132
396088561885459/9999999

result:

ok 3 lines

Test #23:

score: 0
Accepted
time: 73ms
memory: 81536kb

input:

47 9999999 136137
4289563 4425699 4561836 4697971 4834109 4970244 5106380 5242517 5378656 5514792 5650929 5787066 5923201 6059340 6195478 6331614 6467749 6603885 6740022 6876158 7012294 7148432 7284569 7420708 7556845 7692980 7829117 7965255 8101392 8237527 8373666 8509803 8645940 8782078 8918217 90...

output:

15717751
20136134
63276778032658/3333333

result:

ok 3 lines

Test #24:

score: 0
Accepted
time: 88ms
memory: 81576kb

input:

100 9999991 4999996
42 5000037 42 5000037 42 5000037 42 5000037 42 5000037 42 5000037 42 5000037 42 5000037 42 5000037 42 5000037 42 5000037 42 5000037 42 5000037 42 5000037 42 5000037 42 5000037 42 5000037 42 5000037 42 5000037 42 5000037 42 5000037 42 5000037 42 5000037 42 5000037 42 5000037 42 50...

output:

994999105
1004999095
999999100/1

result:

ok 3 lines