QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #180757 | #6416. Classical Scheduling Problem | Curious_Droid | RE | 1ms | 3400kb | C++23 | 8.9kb | 2023-09-16 11:45:18 | 2023-09-16 11:45:19 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define int long long
pair<pair<int, int>, int> topics[200001];
int n, t;
bool check(int x)
{
if (x == 0)
{
return true;
}
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;
}
// 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 = priority_queue<int>();
for (int i = n - 1; i >= 0; i--)
{
suffix[i] = sum;
int a = topics[i].first.second;
int b = topics[i].first.first;
if (b <= x)
{
suffix[i] = 0;
}
else
{
// cout << b-x << "<-\n";
if (pq.size() != b - x)
{
// cout << "setting " << i << " to -1\n";
suffix[i] = -1;
}
}
if (i == 0)
{
break;
}
b = topics[i - 1].first.first;
if (b <= x)
{
continue;
}
// cout << "HERE\n";
// 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);
}
}
}
// 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;
// cout << i << ": " << prefix[i] << " " << a << " " << suffix[i] << "\n";
// cout << b << " " << x << "\n";
if (prefix[i] != -1 && suffix[i] != -1 && prefix[i] + a + suffix[i] <= t)
{
// cout << "ANS aT " << i << "\n";
// cout << prefix[i] << " " << a <<" " << suffix[i] << "\n";
// cout << b << "\n";
return true;
}
}
return false;
}
int calcans(int x)
{
if (x == 0)
{
return -1;
}
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;
}
// 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 = priority_queue<int>();
for (int i = n - 1; i >= 0; i--)
{
suffix[i] = sum;
int a = topics[i].first.second;
int b = topics[i].first.first;
if (b <= x)
{
suffix[i] = 0;
}
else
{
if (pq.size() != b - x)
{
// cout << "setting " << i << " to -1\n";
suffix[i] = -1;
}
}
if (i == 0)
{
break;
}
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)
{
cout << "0\n";
return;
}
// cout << k << " HERE\n";
priority_queue<pair<int, int>> pq;
int sum = 0;
int prefix[n];
for (int i = 0; i < k; i++)
{
// 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});
}
}
// cout << "GOTHERE\n";
}
int suffix[n];
sum = 0;
priority_queue<pair<int, int>> pq2;
// cout << "HERE\n";
for (int i = n - 1; i > k; i--)
{
suffix[i] = sum;
// cout << i << " HERE\n";
int a = topics[i].first.second;
int b = topics[i].first.first;
int id = topics[i].second;
if (b <= x)
{
suffix[i] = 0;
}
else
{
// cout << "GOTHERE\n";
// cout << b << " " << x << "\n";
if (pq.size() != b - x)
{
// cout << "setting " << i << " to -1\n";
suffix[i] = -1;
}
}
if (i == 0)
{
break;
}
b = topics[i - 1].first.first;
if (b <= x)
{
continue;
}
while (pq2.size() > b - x)
{
sum -= pq2.top().first;
pq2.pop();
}
// cout << "GOTHERE2\n";
if (pq2.size() < b - x)
{
pq2.push({a, id});
sum += a;
}
else
{
// cout << "HERE\n";
if (pq2.top().first > a)
{
sum += a;
sum -= pq.top().first;
pq2.pop();
pq2.push({a, id});
}
}
// cout << "GOTHERE3\n";
}
vector<int> v;
while (pq.size() != 0)
{
v.push_back(pq.top().second + 1);
// cout << pq.top().second+1 << "<-\n";
pq.pop();
}
if (topics[k].first.first > x)
{
while (pq2.size() != 0)
{
v.push_back(pq2.top().second + 1);
// cout << pq2.top().second+1 << "<-\n";
pq2.pop();
}
}
v.push_back(topics[k].second + 1);
sort(v.begin(), v.end());
cout << v.size() << "\n";
for (int i : v)
{
cout << i << " ";
}
cout << "\n";
}
signed main()
{
int q;
cin >> q;
while (q--)
{
cin >> n >> t;
// pair<pair<int, int>, int> topics[n];
for (int i = 0; i < n; i++)
{
cin >> topics[i].first.second >> topics[i].first.first;
topics[i].second = i;
}
sort(topics, topics + n);
// for (int i = 0; i < n; i++)
// {
// 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;
// cout << l << " " << r << " " << mid << "\n";
bool res = check(mid);
// cout<< res << "\n";
if (check(mid))
{
l = mid;
}
else
{
r = mid - 1;
}
}
cout << l << "\n";
getans(l);
cout.flush();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3400kb
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 ...