QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #775976 | #9574. Strips | swan416 | WA | 18ms | 3784kb | C++20 | 3.8kb | 2024-11-23 17:11:15 | 2024-11-23 17:11:15 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <map>
#include <cstring>
#include <string>
#include <vector>
#include <cctype>
#include <cmath>
#include <queue>
#include <set>
#include <functional>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
#define qwq ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define tcase \
LL t = read(); \
while (t--)
LL read()
{
LL sum = 0, fl = 1;
int ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-')
fl = -1;
for (; isdigit(ch); ch = getchar())
sum = sum * 10 + ch - '0';
return sum * fl;
}
void solve()
{
LL n = read(), m = read(), k = read(), w = read();
vector<LL> a(n + 1), b(m + 2);
for (int i = 1; i <= n; i++)
a[i] = read();
for (int i = 1; i <= m; i++)
b[i] = read();
m++;
b[m] = w + 1;
sort(a.begin() + 1, a.end());
sort(b.begin() + 1, b.end());
LL lastpos = 1;
LL idxa = 1;
LL ans = 0;
set<PLL> ansset;
// printf("out\n");
for (int i = 1; i <= m; i++)
{
LL nowpos = b[i];
// printf("lastpos:%lld nowpos:%lld\n", lastpos, nowpos);
//[lastpos,nowpos)
set<PLL> s;
set<PLL> lasts;
while (a[idxa] < nowpos&&idxa<=n)
{
// 尝试合并
if (s.empty())
{
s.insert({a[idxa], a[idxa]});
idxa++;
continue;
}
auto [l, r] = *s.rbegin();
LL newr = a[idxa];
LL len = newr - l + 1;
if (len <= k)
{
s.erase({l, r});
s.insert({l, newr});
}
else
{
s.insert({newr, newr});
}
idxa++;
}
// de s
// for(auto [l,r]:s)
// {
// printf("l:%lld r:%lld\n", l, r);
// }
if (s.empty())
{
lastpos = nowpos + 1;
continue;
}
LL lll = lastpos;
for (auto [l, r] : s)
{
// printf("l:%lld r:%lld\n", l, r);
if (lasts.empty())
{
// rr>=lll
LL ll = r - k + 1, rr = r;
LL delta = 0;
if (ll < lll)
delta = lll - ll;
lasts.insert({ll + delta, rr + delta});
// printf("delta ll:%lld rr:%lld\n", ll + delta, rr + delta);
if (rr + delta >= nowpos)
{
// printf("l:%lld r:%lld\n", l, r);
printf("-1\n");
return;
}
lll = rr + 1;
continue;
}
auto [_, lll] = *lasts.rbegin();
lll++;
LL ll = r - k + 1, rr = r;
LL delta = 0;
if (ll < lll)
delta = lll - ll;
// printf("l:%lld r:%lld\n", l, r);
// printf("ll:%lld rr:%lld\n", ll, rr);
// printf("delta ll:%lld rr:%lld\n", ll + delta, rr + delta);
if (rr + delta >= nowpos)
{
// printf("rr:%lld delta:%lld nowpos:%lld\n", rr, delta, nowpos);
printf("-1\n");
return;
}
lasts.insert({ll + delta, rr + delta});
lll = rr + 1;
}
ansset.insert(lasts.begin(), lasts.end());
lastpos = nowpos + 1;
}
printf("%lld\n", ansset.size());
for (auto [l, r] : ansset)
printf("%lld ", l);
printf("\n");
}
int main()
{
tcase
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3784kb
input:
4 5 2 3 16 7 11 2 9 14 13 5 3 2 4 11 6 10 2 1 11 2 1 2 6 1 5 3 2 1 2 6 1 5 2
output:
4 1 7 10 14 -1 2 1 4 -1
result:
ok ok 4 cases (4 test cases)
Test #2:
score: -100
Wrong Answer
time: 18ms
memory: 3740kb
input:
11000 3 8 2 53 32 3 33 35 19 38 20 1 30 10 6 7 10 1 42 3 14 4 36 28 40 22 17 20 12 41 27 7 1 19 13 9 6 6 13 78 55 76 53 32 54 58 62 45 21 4 7 61 8 7 3 68 9 26 54 31 22 3 38 65 34 16 58 47 52 29 53 5 8 4 33 33 5 30 6 15 27 12 9 28 19 2 13 10 6 1 2 48 8 12 48 1 41 31 40 7 6 7 61 20 19 30 52 49 17 40 3...
output:
2 2 32 7 3 4 14 22 28 36 40 3 22 46 64 8 1 7 20 24 30 36 54 63 3 3 14 30 6 1 7 11 30 41 47 4 14 27 34 47 2 42 65 1 27 1 9 1 62 5 24 33 42 47 60 2 3 31 3 11 19 29 3 2 15 33 3 25 30 42 3 2 17 59 4 1 11 21 32 2 53 65 3 49 58 65 3 43 60 78 1 78 4 1 11 15 21 5 3 7 17 36 48 2 1 44 ...
result:
wrong answer Participant didn't find a solution but the jury found one. (test case 73)