Submission #1247809

#TimeUsernameProblemLanguageResultExecution timeMemory
1247809lukavNile (IOI24_nile)C++20
30 / 100
61 ms14212 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define vec vector string to_string(pair<int, int> numbers) { return '(' + to_string(numbers.first) + ", " + to_string(numbers.second) + ')'; } string to_string(vec<int> numbers) { string text = "{"; for (auto i = numbers.begin(); i != numbers.end(); i++) { text += to_string(*i); if (next(i) != numbers.end()) {text += ", ";} } text += '}'; return text; } string to_string(unordered_map<int, int> numbers) { string text = "{"; for (auto i = numbers.begin(); i != numbers.end(); i++) { text += to_string(*i); if (next(i) != numbers.end()) {text += ", ";} } text += '}'; return text; } string to_string(vec<ll> numbers) { string text = "{"; for (auto i = numbers.begin(); i != numbers.end(); i++) { text += to_string(*i); if (next(i) != numbers.end()) {text += ", ";} } text += '}'; return text; } string to_string(vec<pair<int, int>> numbers) { string text = "{"; for (auto i = numbers.begin(); i != numbers.end(); i++) { text += to_string(*i); if (next(i) != numbers.end()) {text += ", ";} } text += '}'; return text; } //bool comp(int a, int b) {return a > b;} vec<ll> calculate_costs(vec<int> W, vec<int> A, vec<int> B, vec<int> E) { int n = W.size(), q = E.size(); vec<int> Ecopy = E; sort(Ecopy.begin(), Ecopy.end()); //cout << to_string(Ecopy) << endl << to_string(E); ll constant = 0; bool areallones = true; for (int i = 0; i < n; i++) { constant += B[i]; A[i] -= B[i]; if (A[i] != 1 || B[i] != 1) {areallones = false;} } vec<pair<int, int>> artifacts; for (int i = 0; i < n; i++) { artifacts.push_back(make_pair(W[i], A[i])); } sort(artifacts.begin(), artifacts.end()); //cout << to_string(artifacts) << endl; //vec<pair<vec<pair<int, int>> , vec<int> >> //vec of pairvec (artifacts, otherinfo) //cout << to_string(artifacts); //cout << constant << endl << to_string(A) << to_string(B); vec<ll> answers; if (!areallones) { for (int i = 0; i < q; i++) { int D = E[i]; ll answ = constant; int minimum = artifacts[0].second; int index = 0; if (n == 1) {answ += minimum;} for (int j = 1; j < n; j++) { if (artifacts[j].first - artifacts[j - 1].first > D) { if ((j - index) % 2 == 1) {answ += minimum;} minimum = artifacts[j].second; index = j; } else { if (artifacts[j].second < minimum && (j == n - 1 || (j - index) % 2 == 0 || artifacts[j + 1].first - artifacts[j - 1].first <= D)) { minimum = artifacts[j].second; } } if (j == n - 1) {if ((j - index) % 2 == 0) {answ += minimum;}} } answers.push_back(answ);//cout << answ << endl; } } else { unordered_map<int, int> Dtoansw, intervals, intervalsbackwards; vec<pair<int, int>> diffindex; ll answ = constant * 2; for (int i = 0; i < n; i++) { intervals[i] = i; intervalsbackwards[i] = i; } for (int i = 0; i < n - 1; i++) { int diff = artifacts[i + 1].first - artifacts[i].first; diffindex.push_back(make_pair(diff, i)); } sort(diffindex.begin(), diffindex.end()); int indexthroughout = 0; //cout << to_string(artifacts); for (int i = 0; i < q; i++) { int D = Ecopy[i]; if (Dtoansw.find(D) == Dtoansw.end()) { if (indexthroughout >= n) {i = q;} else { while (diffindex[indexthroughout].first <= D) { //cout << answ << endl << to_string(intervals) << " - intervals" << endl << to_string(intervalsbackwards) << "- intervalsbackwards" << endl << to_string(diffindex) << "- diffindex" << endl << endl; // Merge int a = diffindex[indexthroughout].second; int k = intervalsbackwards[a]; int j = intervals[a + 1]; intervals[k] = j; intervalsbackwards[j] = k; intervalsbackwards.erase(a); intervals.erase(a + 1); if ((j - a) % 2 == 1 && (a - k + 1) % 2 == 1) { answ -= 2; } indexthroughout++; } } } answers.push_back(answ); } } //cout << to_string(answers); return answers; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...