QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#184085 | #6417. Classical Summation Problem | Pentagonal | WA | 0ms | 3876kb | C++17 | 7.3kb | 2023-09-20 12:08:28 | 2023-09-20 12:08:29 |
Judging History
answer
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
//Template {
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
//IO templates
//Note: use endl only for interactive problems or to debug segfaults; use newl for other problems
#define newl "\n"
#define fastIO ios::sync_with_stdio(false); cin.tie(nullptr)
#define fileIO(x) ifstream fin((str) x + (str) ".in"); ofstream fout((str) x + (str) ".out");
// void fileIO(string x) {}
#define flush() fflush(stdout)
#define interact(n) fflush(stdout); cin >> n; if (n == -1) return 0
#define testcases int tt; cin >> tt; fun(i, tt) solve();
#define vectorIO(n, MikuBondage) fun(j, n) {int i; cin >> i; MikuBondage.pb(i);}
#define vector2IO(n, MikuBondage) fun(j, n) {int i, ii; cin >> i >> ii; MikuBondage.pb(mp(i, ii));}
#define edgeIO(m) fun(i, m) {int a, b; cin >> a >> b; addEdges(a, b);}
#define WeightedEdgeIO(m) fun(i, m) {int a, b, c; cin >> a >> b >> c; addWeightedEdges(a, b, c);}
//types
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define ld long double
#define str string
//vector
#define pb push_back
#define append push_back
//pairs
#define mp make_pair
#define p2 pair<int, int>
#define p3 pair<int, p2>
#define m3(x, y, z) mp(x, mp(y, z))
#define ich first
#define ni second.first
#define sanshi second.second
//For loops
#define ahegao(i, a, b) for (int i = a; i < b; i++)
#define baka(i, b, a) for (int i = b; i > a; i--)
#define fun(i, n) for (int i = 1; i <= (n); (i)++)
#define fon(i, n) for (int i = 0; i < (n); (i)++)
#define fur(i, n) for (auto i : (n))
//Sorts
#define sz(a) ((signed) a.size())
#define all(a) a.begin(), a.end()
#define Sort(a) sort((a).begin(), (a).end())
#define rSort(a) sort((a).rbegin(), (a).rend())
#define clamp(x, y) (x) = min((int) (x), (int) (y))
#define CLAMP(x, y) (x) = max((int) (x), (int) (y))
//Other stuff
#define elif else if
#define addEdges(a, b) adj[a].pb(b); adj[b].pb(a)
#define addWeightedEdges(a, b, c) adj[a].pb(mp(b, c)); adj[b].pb(mp(a, c))
// #define find find_by_order
#define printLength(x) if (x < INF) cout << x << newl; else cout << -1 << newl;
#define printVector(a) fur(i, a) cout << i << ' '; cout << newl;
// void printRange(vector<int>::iterator left, vector<int>::iterator right) {
// for (auto i = left; i < right; i++) cout << *i << ' ';
// cout << newl;
// }
//Constants
const int MOD = 998244353; //
// const int SMALLMOD = 998244353;
const int INF = 2e9+1337;
const ll EXCEED = 2e18+1337;
const ll GRAVITY = 9e18;
/*
Pro Tips:
1. Print the whole array at once don't be blinded by bad debug
2. Look at the testcases to see what went wrong
3. Pay attention to the order of operations
4. Modify pointers outside of functions
5. Always remember to save.
*/
#define int ll
//}
const int MAX = 200005;
int n, t;
vector<p3> MikuBondage;
bool check(int k, bool final) {
// cout << "\n== CHECKING FOR " << k << " ==\n\n";
if (k == 0) {
if (final) {
cout << "0\n0\n\n";
}
return true;
}
set<p3> understand, learn, other;
other.insert(all(MikuBondage));
int curr_time = 0;
int pointer = 0;
fun(b, n) {
while (understand.size() + learn.size() < b and other.size() > 0) {
learn.insert(*other.begin());
curr_time += (*other.begin()).first;
other.erase(other.begin());
}
while (pointer < n) {
if (MikuBondage[pointer].second.first <= b) {
if (learn.find(MikuBondage[pointer]) != learn.end()) {
understand.insert(*learn.find(MikuBondage[pointer]));
learn.erase(learn.find(MikuBondage[pointer]));
}
if (other.find(MikuBondage[pointer]) != other.end()) {
understand.insert(*other.find(MikuBondage[pointer]));
curr_time += (*other.find(MikuBondage[pointer])).first;
other.erase(other.find(MikuBondage[pointer]));
// cout << "GOOD";
}
pointer++;
} else {
break;
}
}
// cout << curr_time << newl;
while (understand.size() > k) {
learn.insert(*understand.rbegin());
understand.erase(prev(understand.end()));
}
while (understand.size() + learn.size() > b and learn.size() >= 1) {
other.insert(*learn.rbegin());
curr_time -= (*learn.rbegin()).first;
learn.erase(prev(learn.end()));
}
while (learn.size() >= 1 and other.size() >= 1) {
// cout << (*other.begin()).first - (*learn.rbegin()).first << newl;
if (*learn.rbegin() > *other.begin()) {
curr_time += (*other.begin()).first - (*learn.rbegin()).first;
p3 temp = *other.begin();
other.erase(*other.begin());
other.insert(*learn.rbegin());
learn.erase(prev(learn.end()));
learn.insert(temp);
while (understand.size() + learn.size() < b and other.size() > 0) {
learn.insert(*other.begin());
curr_time += (*other.begin()).first;
other.erase(other.begin());
}
} else break;
}
// cout << b << ' ' << curr_time << newl;
// cout << "UNDERSTAND" << newl;
// fur(i, understand) cout << i.first << ' ' << i.second.first << newl;
// cout << "LEARN" << newl;
// fur(i, learn) cout << i.first << ' ' << i.second.first << newl;
// cout << "UNLEARNED" << newl;
// fur(i, other) cout << i.first << ' ' << i.second.first << newl;
// cout << newl;
if (understand.size() == k and curr_time <= t) {
if (final) {
cout << k << newl << learn.size() + understand.size() << newl;
fur(i, understand) cout << i.second.second << ' ';
fur(i, learn) cout << i.second.second << ' ';
cout << newl;
// cout << k << newl;
}
return true;
}
// cout << curr_time << newl;
}
return false;
}
bool compare(p3 a, p3 b) {
if (a.second.first == b.second.first) return a.first < b.first;
return a.second.first < b.second.first;
}
void solve() {
MikuBondage.clear();
cin >> n >> t;
fun(i, n) {
int a, b;
cin >> a >> b;
MikuBondage.pb(mp(a, mp(b, i)));
}
sort(all(MikuBondage), compare);
int l = 0;
int r = n;
while (l < r) {
int mid = (l + r + 1) / 2;
if (check(mid, false)) {
l = mid;
} else {
r = mid - 1;
}
}
check(l, true);
}
signed main() {
fastIO;
testcases;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3876kb
input:
3 2
output:
0 0 0 0 0 0
result:
wrong answer 1st numbers differ - expected: '14', found: '0'