QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #404320 | #7744. Elevator | writingdog# | WA | 35ms | 7884kb | C++20 | 9.1kb | 2024-05-03 19:40:33 | 2024-05-03 19:40:34 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
typedef unsigned long long ull;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
int f[N][2];
int sumef[N];
void solve()
{
int n, k;
cin >> n >> k;
vector<int> idx0, idx1;
int alle = 0;
vector <int> c(n+1),w(n+1),ff(n+1);
for (int i = 1; i <= n; ++i)
{
// int c, w, ff;
cin >> c[i] >> w[i] >> ff[i];
if (w[i] % 2 == 1)
{
if (!sumef[ff[i]])
idx1.emplace_back(ff[i]);
sumef[ff[i]] += c[i];
alle++;
}
else
{
if (!f[ff[i]][0])
idx0.emplace_back(ff[i]);
f[ff[i]][0] += c[i];
}
}
// cout << "test1 \n";
if (alle % 2 == 0)
{
k /= 2;
int o = N - 1, e = N - 1;
int resv = 0;
int resc = 0;
sort(idx1.begin(), idx1.end());
reverse(idx1.begin(), idx1.end());
for (auto e : idx1)
{
// while (e >= 1 && sumef[e] == 0)
// e--;
// if (e < 1)
// break;
// cout << e << " ";
if (resc == 0)
{
if (sumef[e] / 2 >= 1)
{
if (!f[e][0])
idx0.emplace_back(e);
f[e][0] += sumef[e] / 2;
}
sumef[e] %= 2;
if (sumef[e])
{
resc = 1;
resv = e;
sumef[e] = 0;
}
}
else
{
sumef[e]--;
if (!f[resv][0])
idx0.emplace_back(resv);
f[resv][0]++;
resc = 0;
if (sumef[e] / 2 >= 1)
{
if (!f[e][0])
idx0.emplace_back(e);
f[e][0] += sumef[e] / 2;
}
sumef[e] %= 2;
if (sumef[e])
{
resc = 1;
resv = e;
sumef[e] = 0;
}
}
}
// cout << endl;
int ans = 0;
if (resc)
{
ans += resv;
}
// while (o >= 1 && f[o][0] == 0)
// o--;
sort(idx0.begin(), idx0.end());
reverse(idx0.begin(), idx0.end());
resv = 0;
resc = 0;
for (auto o : idx0)
{
// cerr << o << " " << f[o][0] << endl;
if (resc == 0)
{
ans += f[o][0] / k * o;
f[o][0] %= k;
resc = f[o][0];
resv = o;
f[o][0] = 0;
}
else
{
if (resc + f[o][0] <= k)
{
resc += f[o][0];
f[o][0] = 0;
continue;
}
f[o][0] -= (k - resc);
ans += resv;
resv = -1;
resc = 0;
ans += f[o][0] / k * o;
f[o][0] %= k;
resc = f[o][0];
resv = o;
f[o][0] = 0;
}
}
if (resc)
{
ans += resv;
}
cout << ans << endl;
}
int fans = 0;
k /= 2;
int o = N - 1, e = N - 1;
int resv = 0;
int resc = 0;
sort(idx1.begin(), idx1.end());
reverse(idx1.begin(), idx1.end());
for (auto e : idx1)
{
// while (e >= 1 && sumef[e] == 0)
// e--;
// if (e < 1)
// break;
// cout << e << " ";
if (resc == 0)
{
if (sumef[e] / 2 >= 1)
{
if (!f[e][0])
idx0.emplace_back(e);
f[e][0] += sumef[e] / 2;
}
sumef[e] %= 2;
if (sumef[e])
{
resc = 1;
resv = e;
sumef[e] = 0;
}
}
else
{
sumef[e]--;
if (!f[resv][0])
idx0.emplace_back(resv);
f[resv][0]++;
resc = 0;
if (sumef[e] / 2 >= 1)
{
if (!f[e][0])
idx0.emplace_back(e);
f[e][0] += sumef[e] / 2;
}
sumef[e] %= 2;
if (sumef[e])
{
resc = 1;
resv = e;
sumef[e] = 0;
}
}
}
// cout << endl;
int ans = 0;
if (resc)
{
ans += resv;
}
// while (o >= 1 && f[o][0] == 0)
// o--;
sort(idx0.begin(), idx0.end());
reverse(idx0.begin(), idx0.end());
resv = 0;
resc = 0;
for (auto o : idx0)
{
// cerr << o << " " << f[o][0] << endl;
if (resc == 0)
{
ans += f[o][0] / k * o;
f[o][0] %= k;
resc = f[o][0];
resv = o;
f[o][0] = 0;
}
else
{
if (resc + f[o][0] <= k)
{
resc += f[o][0];
f[o][0] = 0;
continue;
}
f[o][0] -= (k - resc);
ans += resv;
resv = -1;
resc = 0;
ans += f[o][0] / k * o;
f[o][0] %= k;
resc = f[o][0];
resv = o;
f[o][0] = 0;
}
}
if (resc)
{
ans += resv;
}
fans = ans;
//
idx0.clear();
idx1.clear();
//////////////////
for (int i = 1; i <= n; ++i)
{
// int c, w, ff;
if (w[i] % 2 == 1)
{
if (!sumef[ff[i]])
idx1.emplace_back(ff[i]);
sumef[ff[i]] += c[i];
alle++;
}
else
{
if (!f[ff[i]][0])
idx0.emplace_back(ff[i]);
f[ff[i]][0] += c[i];
}
}
// k /= 2;
resv = 0;
resc = 0;
sort(idx1.begin(), idx1.end());
reverse(idx1.begin(), idx1.end());
int fir=1;
for (auto e : idx1)
{
if(fir==1)
{
ans+=e;
sumef[e]--;
if(sumef[e]==0) continue;
fir=0;
}
if (resc == 0)
{
if (sumef[e] / 2 >= 1)
{
if (!f[e][0])
idx0.emplace_back(e);
f[e][0] += sumef[e] / 2;
}
sumef[e] %= 2;
if (sumef[e])
{
resc = 1;
resv = e;
sumef[e] = 0;
}
}
else
{
sumef[e]--;
if (!f[resv][0])
idx0.emplace_back(resv);
f[resv][0]++;
resc = 0;
if (sumef[e] / 2 >= 1)
{
if (!f[e][0])
idx0.emplace_back(e);
f[e][0] += sumef[e] / 2;
}
sumef[e] %= 2;
if (sumef[e])
{
resc = 1;
resv = e;
sumef[e] = 0;
}
}
}
// cout << endl;
ans = 0;
if (resc)
{
ans += resv;
}
// while (o >= 1 && f[o][0] == 0)
// o--;
sort(idx0.begin(), idx0.end());
reverse(idx0.begin(), idx0.end());
resv = 0;
resc = 0;
for (auto o : idx0)
{
// cerr << o << " " << f[o][0] << endl;
if (resc == 0)
{
ans += f[o][0] / k * o;
f[o][0] %= k;
resc = f[o][0];
resv = o;
f[o][0] = 0;
}
else
{
if (resc + f[o][0] <= k)
{
resc += f[o][0];
f[o][0] = 0;
continue;
}
f[o][0] -= (k - resc);
ans += resv;
resv = -1;
resc = 0;
ans += f[o][0] / k * o;
f[o][0] %= k;
resc = f[o][0];
resv = o;
f[o][0] = 0;
}
}
if (resc)
{
ans += resv;
}
fans=min(ans,fans);
}
signed main()
{
// cout.flags(ios::fixed); cout.precision(8);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
cin >> T;
for (int i = 1; i <= T; ++i)
{
solve();
}
return 0;
}
/*
2
4 6
1 1 8
7 2 5
1 1 7
3 2 6
8 1200000
100000 1 100000
100000 1 12345
100000 2 100000
100000 2 12345
100000 1 100000
100000 1 12345
100000 2 100000
100000 2 12345
1
4 6
1 1 8
7 2 5
1 1 7
3 2 6
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3536kb
input:
2 4 6 1 1 8 7 2 5 1 1 7 3 2 6 8 1200000 100000 1 100000 100000 1 12345 100000 2 100000 100000 2 12345 100000 1 100000 100000 1 12345 100000 2 100000 100000 2 12345
output:
24 100000
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 35ms
memory: 7884kb
input:
5501 8 104 5 2 3 6 2 4 5 2 3 6 2 9 8 2 4 2 1 3 7 2 4 8 2 8 1 290 3 1 1 12 12 6 1 2 1 2 2 1 1 2 1 2 4 6 1 1 1 2 5 6 1 4 4 1 4 6 2 4 6 2 5 4 2 5 4 1 4 5 334 1 1 4 1 2 3 4 2 1 5 1 1 2 1 2 13 218 5 2 3 5 1 4 1 2 1 1 2 5 3 2 2 1 1 3 4 2 2 1 2 5 2 2 1 2 1 5 3 2 1 5 2 1 1 1 4 10 260 7 2 1 5 1 1 5 2 4 6 1 6...
output:
24 8 7 1 11 1 10 7 12 20 1 11 5 7 6 3 3 4 3 5 11 10 10 9 7 5 3 8 7 9 5 3 9 2 9 8 12 18 8 5 11 9 2 3 5 4 8 6 5 2 8 1 3 2 1 6 2 7 2 7 5 5 21 3 9 5 6 5 9 4 8 2 2 8 7 11 8 10 4 11 1 3 9 5 14 6 1 3 4 5 6 17 5 3 8 6 1 4 2 13 6 26 2 35 8 21 11 5 10 9 9 8 6 2 13 1 19 7 7 2 3 21 92 11 1 4 4 3 4 3 3 7 3 2 3 4...
result:
wrong answer 1st lines differ - expected: '9', found: '24'