QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#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

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

[2024-11-23 17:11:15]
评测

测评结果：WA
用时：18ms
内存：3784kb

查看

[2024-11-23 17:11:15]
提交

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;
}

源文件, 语言: C++20

详细

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:

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)