QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#179958#6416. Classical Scheduling ProblemCurious_DroidRE 1ms3436kbC++238.7kb2023-09-15 13:56:102023-09-15 13:56:10

Judging History

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

  • [2023-09-15 13:56:10]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3436kb
  • [2023-09-15 13:56:10]
  • 提交

answer

#include <iostream>
#include <algorithm>
#include <queue>

#define int long long

std::pair<std::pair<int, int>, int> topics[200001];

int n, t;

bool check(int x)
{
    if(x == 0){
        return true;
    }
    std::priority_queue<int> pq;
    int sum = 0;
    int prefix[n];
    for (int i = 0; i < n; i++)
    {
        if(x == 1){
            prefix[i] = 0;
            continue;
        }
        prefix[i] = sum;
        if(pq.size() != x - 1){
            prefix[i] = -1;
        }
        //std::cout << i << ": " << prefix[i] << "\n";
        int a = topics[i].first.second;
        if (pq.size() < x - 1)
        {
            pq.push(a);
            sum += a;
        }
        else
        {
            if (pq.top() > a)
            {
                sum += a;
                sum -= pq.top();
                pq.pop();
                pq.push(a);
            }
        }
    }
    int suffix[n];
    sum = 0;
    pq = std::priority_queue<int>();
    for (int i = n - 1; i >= 0; i--)
    {
        suffix[i] = sum;
        if (i == 0)
        {
            break;
        }
        int a = topics[i].first.second;
        int b = topics[i].first.first;
        if (b <= x)
        {
            suffix[i] = 0;
            continue;
        }
        //std::cout << b-x << "<-\n";
        if(pq.size() != b - x){
            //std::cout << "setting " << i << " to -1\n";
            suffix[i] = -1;
        }
        b = topics[i-1].first.first;
        if (b <= x)
        {
            continue;
        }
        //std::cout << "HERE\n";
        //std::cout << "HERE\n";
        while (pq.size() > b - x)
        {
            sum -= pq.top();
            pq.pop();
        }
        if (pq.size() < b - x)
        {
            pq.push(a);
            sum += a;
        }
        else
        {
            if (pq.top() > a)
            {
                sum += a;
                sum -= pq.top();
                pq.pop();
                pq.push(a);
            }
        }
    }

    //std::cout << "PRINTING\n";

    for (int i = x - 1; i < n; i++)
    {
        int b = topics[i].first.first;
        if (b <= x)
        {
            continue;
        }
        int a = topics[i].first.second;
        // std::cout << i << ": " << prefix[i] << " " << a << " " << suffix[i] << "\n";
        // std::cout << b << " " << x << "\n";
        if (prefix[i] != -1 && suffix[i] != -1 && prefix[i] + a + suffix[i] <= t)
        {
            // std::cout << "ANS aT " << i << "\n";
            // std::cout << prefix[i] << " " << a <<" " << suffix[i] << "\n";
            // std::cout << b << "\n";
            return true;
        }
    }
    return false;
}

int calcans(int x)
{
    std::priority_queue<int> pq;
    int sum = 0;
    int prefix[n];
    for (int i = 0; i < n; i++)
    {
        if(x == 1){
            prefix[i] = 0;
            continue;
        }
        prefix[i] = sum;
        if(pq.size() != x - 1){
            prefix[i] = -1;
        }
        //std::cout << i << ": " << prefix[i] << "\n";
        int a = topics[i].first.second;
        if (pq.size() < x - 1)
        {
            pq.push(a);
            sum += a;
        }
        else
        {
            if (pq.top() > a)
            {
                sum += a;
                sum -= pq.top();
                pq.pop();
                pq.push(a);
            }
        }
    }
    int suffix[n];
    sum = 0;
    pq = std::priority_queue<int>();
    for (int i = n - 1; i >= 0; i--)
    {
        suffix[i] = sum;
        if (i == 0)
        {
            break;
        }
        int a = topics[i].first.second;
        int b = topics[i].first.first;
        if (b <= x)
        {
            suffix[i] = 0;
            continue;
        }
        if(pq.size() != b - x){
            //std::cout << "setting " << i << " to -1\n";
            suffix[i] = -1;
        }
        b = topics[i-1].first.first;
        if (b <= x)
        {
            continue;
        }
        while (pq.size() > b - x)
        {
            sum -= pq.top();
            pq.pop();
        }
        if (pq.size() < b - x)
        {
            pq.push(a);
            sum += a;
        }
        else
        {
            if (pq.top() > a)
            {
                sum += a;
                sum -= pq.top();
                pq.pop();
                pq.push(a);
            }
        }
    }

    for (int i = x - 1; i < n; i++)
    {
        int b = topics[i].first.first;
        if (b <= x)
        {
            continue;
        }
        int a = topics[i].first.second;
        if (prefix[i] != -1 && suffix[i] != -1 && prefix[i] + a + suffix[i] <= t)
        {
            return i;
        }
    }
    return -1;
}

void getans(int x)
{
    int k = calcans(x);
    if(k == -1){
        std::cout << "0\n";
        return;
    }
    //std::cout << k << " HERE\n";
    std::priority_queue<std::pair<int, int>> pq;
    int sum = 0;
    int prefix[n];
    for (int i = 0; i < k; i++)
    {
    //std::cout << i << " HERE\n";
        if(x == 1){
            prefix[i] = 0;
            continue;
        }
        prefix[i] = sum;
        if(pq.size() != x - 1){
            prefix[i] = -1;
        }
        int a = topics[i].first.second;
        int id = topics[i].second;
        if (pq.size() < x - 1)
        {
            pq.push({a, id});
            sum += a;
        }
        else
        {
            if (pq.top().first > a)
            {
                sum += a;
                sum -= pq.top().first;
                pq.pop();
                pq.push({a, id});
            }
        }
        //std::cout << "GOTHERE\n";
    }
    int suffix[n];
    sum = 0;
    std::priority_queue<std::pair<int, int>> pq2;
    //std::cout << "HERE\n";
    for (int i = n - 1; i > k; i--)
    {
        suffix[i] = sum;
    //std::cout << i << " HERE\n";
        if (i == 0)
        {
            break;
        }
        int a = topics[i].first.second;
        int b = topics[i].first.first;
        int id = topics[i].second;
        if (b <= x)
        {
            suffix[i] = 0;
            continue;
        }
        //std::cout << "GOTHERE\n";
        //std::cout << b << " " << x << "\n";
        if(pq.size() != b - x){
            //std::cout << "setting " << i << " to -1\n";
            suffix[i] = -1;
        }
        b = topics[i-1].first.first;
        if (b <= x)
        {
            continue;
        }
        while (pq2.size() > b - x)
        {
            sum -= pq2.top().first;
            pq2.pop();
        }
        //std::cout << "GOTHERE2\n";
        if (pq2.size() < b - x)
        {
            pq2.push({a, id});
            sum += a;
        }
        else
        {
            //std::cout << "HERE\n";
            if (pq2.top().first > a)
            {
                sum += a;
                sum -= pq.top().first;
                pq2.pop();
                pq2.push({a, id});
            }
        }
        //std::cout << "GOTHERE3\n";
    }

    std::vector<int> v;
    while(pq.size() != 0){
        v.push_back(pq.top().second+1);
        //std::cout << pq.top().second+1 << "<-\n";
        pq.pop();
    }
    while(pq2.size() != 0){
        v.push_back(pq2.top().second+1);
        //std::cout << pq2.top().second+1 << "<-\n";
        pq2.pop();
    }
    v.push_back(topics[k].second+1);
    std::sort(v.begin(), v.end());
    std::cout << v.size() << "\n";
    for(int i : v){
        std::cout << i << " ";
    }
    std::cout << "\n";
}

signed main()
{
    int q;
    std::cin >> q;
    while (q--)
    {
        std::cin >> n >> t;
        //std::pair<std::pair<int, int>, int> topics[n];
        for (int i = 0; i < n; i++)
        {
            std::cin >> topics[i].first.second >> topics[i].first.first;
            topics[i].second = i;
        }
        std::sort(topics, topics + n);
        // for (int i = 0; i < n; i++)
        // {
        //     std::cout << i << ": " << topics[i].first.second << " " << topics[i].first.first << " " << topics[i].second <<"\n";
        // }

        int l = 0, r = n;
        while (l < r)
        {
            int mid = (l + r) / 2 + 1;
            //std::cout << l << " " << r << " " << mid << "\n";
            bool res = check(mid);
            //std::cout<< res << "\n";
            if (check(mid))
            {
                l = mid;
            }
            else
            {
                r = mid - 1;
            }
        }
        std::cout << l << "\n";
        getans(l);
        std::cout.flush();
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3436kb

input:

2
4 100
20 1
40 4
60 3
30 3
1 5
10 1

output:

2
3
1 2 4 
0
0

result:

ok ok, 2 test cases (2 test cases)

Test #2:

score: -100
Runtime Error

input:

10000
21 1892
174 13
604 15
170 2
413 11
899 2
531 12
651 17
553 9
429 8
837 14
937 12
577 7
532 11
19 2
173 10
165 6
762 15
221 6
945 13
302 19
7 3
54 26066
812 31
432 24
240 37
171 39
204 47
174 30
569 1
467 5
624 42
734 35
907 3
568 23
802 40
991 32
119 13
187 27
739 42
891 14
550 44
374 16
483 1...

output:

7
8
3 9 12 14 15 16 18 21 
47
48
1 2 3 4 5 6 7 8 9 10 12 13 15 16 17 19 20 21 22 24 25 26 27 28 29 30 31 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 51 52 53 54 
10
11
1 3 4 5 6 7 8 12 14 15 16 
7
14
1 8 11 13 14 21 24 28 33 37 38 40 41 43 
8
9
7 9 10 12 15 19 27 28 29 
0
0
10
11
1 2 4 5 6 7 ...

result: