QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#184016#6416. Classical Scheduling ProblemPentagonalWA 0ms3556kbC++176.2kb2023-09-20 10:30:092023-09-20 10:30:10

Judging History

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

  • [2023-09-20 10:30:10]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3556kb
  • [2023-09-20 10:30:09]
  • 提交

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) {
    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]));
                    
                }
                elif (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()));
        }
        // cout << newl << b << ' ' << curr_time << newl;
        // cout << "UNDERSTAND" << newl;
        // fur(i, understand) cout << i.first << ' ' << i.second << newl;
        // cout << "LEARN" << newl;
        // fur(i, learn) cout << i.first << ' ' << i.second << newl;
        
        if (understand.size() == k and curr_time <= t) {
            if (final) {
                cout << k << newl << learn.size() << newl;
                fur(i, understand) cout << i.second.second << ' ';
                fur(i, learn)  cout << i.second.second << ' ';
                cout << 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: 3556kb

input:

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

output:

2
1
1 4 2 
0
0


result:

wrong answer actual and declared scores differ: actual = 1, declared = 2 (test case 1)