| Task: | Muutokset |
| Sender: | Kuha |
| Submission time: | 2025-11-08 15:48:29 +0200 |
| Language: | C++ (C++17) |
| Status: | READY |
| Result: | 0 |
| group | verdict | score |
|---|---|---|
| #1 | WRONG ANSWER | 0 |
| #2 | WRONG ANSWER | 0 |
| #3 | WRONG ANSWER | 0 |
| test | verdict | time | group | |
|---|---|---|---|---|
| #1 | WRONG ANSWER | 0.00 s | 1, 2, 3 | details |
| #2 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
| #3 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
| #4 | WRONG ANSWER | 0.01 s | 1, 2, 3 | details |
| #5 | WRONG ANSWER | 0.01 s | 1, 2, 3 | details |
| #6 | WRONG ANSWER | 0.01 s | 2, 3 | details |
| #7 | WRONG ANSWER | 0.01 s | 2, 3 | details |
| #8 | WRONG ANSWER | 0.01 s | 2, 3 | details |
| #9 | WRONG ANSWER | 0.01 s | 2, 3 | details |
| #10 | ACCEPTED | 0.05 s | 3 | details |
| #11 | WRONG ANSWER | 0.06 s | 3 | details |
| #12 | WRONG ANSWER | 0.06 s | 3 | details |
| #13 | WRONG ANSWER | 0.07 s | 3 | details |
Code
#include <bits/stdc++.h>
#define ll long long
#define N (1<<17)
using namespace std;
ll v[111111];
ll r[111111];
ll l[111111];
ll cnt[N];
int cnts[2 * N];
ll insert(int x) {
int i = 1;
while (i < N) {
if (cnts[2 * i] <= x) {
i = 2 * i;
} else {
i = 2 * i + 1;
}
}
ll ret = i - N;
cnts[i]++;
for (i /= 2; i >= 1; i /= 2) {
cnts[i] = min(cnts[2 * i], cnts[2 * i + 1]);
}
return ret;
}
int main () {
int n, m;
cin>>n>>m;
for (int i = 0; i < m; i++) {
cin>>v[i];
}
ll cost;
for (int i = 0; i <= m; i++) cnt[i] = 0;
for (int i = 0; i < 2 * N; i++) cnts[i] = 0;
cost = 0;
for (int i = 0; i < m; i++) {
cost += insert(cnt[v[i]]++) + 1;
l[i] = cost;
}
reverse(v, v + m);
for (int i = 0; i <= n; i++) cnt[i] = 0;
for (int i = 0; i < 2 * N; i++) cnts[i] = 0;
cost = 0;
for (int i = 0; i < m; i++) {
cost += insert(cnt[v[i]]++) + 1;
r[i] = cost;
}
cout<<l[m - 1]<<" ";
for (int i = 1; i < m - 1; i++) {
cout<<(l[i] + r[m - i - 2])<<" ";
}
cout<<endl;
}Test details
Test 1
Group: 1, 2, 3
Verdict: WRONG ANSWER
| input |
|---|
| 1 1 1 |
| correct output |
|---|
| (empty) |
| user output |
|---|
| 1 |
Feedback: Output is longer than expected
Test 2
Group: 1, 2, 3
Verdict: ACCEPTED
| input |
|---|
| 100 1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
| correct output |
|---|
| 1000 1000 1000 1000 1000 1000 ... |
| user output |
|---|
| 1000 1000 1000 1000 1000 1000 ... |
Test 3
Group: 1, 2, 3
Verdict: ACCEPTED
| input |
|---|
| 100 1000 1 2 2 2 1 1 1 1 1 1 1 1 1 2 1 ... |
| correct output |
|---|
| 1488 1488 1487 1486 1487 1488 ... |
| user output |
|---|
| 1488 1488 1487 1486 1487 1488 ... |
Test 4
Group: 1, 2, 3
Verdict: WRONG ANSWER
| input |
|---|
| 100 1000 7 8 2 4 8 3 3 10 9 7 7 6 8 7 2... |
| correct output |
|---|
| 5107 5107 5103 5099 5098 5102 ... |
| user output |
|---|
| 5109 5107 5103 5099 5098 5102 ... |
Feedback: Incorrect character on line 1 col 4: expected "5107", got "5109"
Test 5
Group: 1, 2, 3
Verdict: WRONG ANSWER
| input |
|---|
| 100 1000 23 85 3 99 63 79 38 37 67 28 7... |
| correct output |
|---|
| 41676 41672 41621 41587 41589 ... |
| user output |
|---|
| 41714 41672 41621 41587 41589 ... |
Feedback: Incorrect character on line 1 col 3: expected "41676", got "41714"
Test 6
Group: 2, 3
Verdict: WRONG ANSWER
| input |
|---|
| 100000 1000 2 1 2 1 1 2 2 2 1 2 2 2 2 2 2 ... |
| correct output |
|---|
| 1484 1485 1484 1485 1485 1485 ... |
| user output |
|---|
| 1485 1485 1484 1485 1485 1485 ... |
Feedback: Incorrect character on line 1 col 4: expected "1484", got "1485"
Test 7
Group: 2, 3
Verdict: WRONG ANSWER
| input |
|---|
| 100000 1000 10 8 4 4 3 8 4 7 5 9 7 1 5 3 4... |
| correct output |
|---|
| 5279 5275 5277 5276 5272 5268 ... |
| user output |
|---|
| 5281 5275 5277 5276 5272 5268 ... |
Feedback: Incorrect character on line 1 col 3: expected "5279", got "5281"
Test 8
Group: 2, 3
Verdict: WRONG ANSWER
| input |
|---|
| 100000 1000 82 63 63 58 57 46 58 40 23 47 ... |
| correct output |
|---|
| 41444 41381 41301 41284 41279 ... |
| user output |
|---|
| 41509 41381 41301 41284 41279 ... |
Feedback: Incorrect character on line 1 col 3: expected "41444", got "41509"
Test 9
Group: 2, 3
Verdict: WRONG ANSWER
| input |
|---|
| 100000 1000 50231 31135 38003 12048 55578 ... |
| correct output |
|---|
| 498503 497507 496513 495521 49... |
| user output |
|---|
| 499501 497507 496513 495521 49... |
Feedback: Incorrect character on line 1 col 3: expected "498503", got "499501"
Test 10
Group: 3
Verdict: ACCEPTED
| input |
|---|
| 100000 100000 1 2 1 2 1 1 2 1 1 1 1 2 1 1 2 ... |
| correct output |
|---|
| 149988 149988 149988 149988 14... |
| user output |
|---|
| 149988 149988 149988 149988 14... |
Test 11
Group: 3
Verdict: WRONG ANSWER
| input |
|---|
| 100000 100000 4 2 6 2 2 2 2 5 9 5 3 5 1 9 1 ... |
| correct output |
|---|
| 547169 547164 547157 547151 54... |
| user output |
|---|
| 547170 547164 547157 547151 54... |
Feedback: Incorrect character on line 1 col 5: expected "547169", got "547170"
Test 12
Group: 3
Verdict: WRONG ANSWER
| input |
|---|
| 100000 100000 15 9 37 82 72 45 42 96 67 99 6... |
| correct output |
|---|
| 4959855 4959845 4959773 495975... |
| user output |
|---|
| 4959890 4959845 4959773 495975... |
Feedback: Incorrect character on line 1 col 6: expected "4959855", got "4959890"
Test 13
Group: 3
Verdict: WRONG ANSWER
| input |
|---|
| 100000 100000 30941 71402 45742 82863 71830 ... |
| correct output |
|---|
| 2378217706 2378191367 23781909... |
| user output |
|---|
| 2378219610 2378191367 23781909... |
Feedback: Incorrect character on line 1 col 7: expected "2378217706", got "2378219610"