API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Feb 28th, 2020
105
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 17.89 KB | None | 0 0
raw download clone embed print report
  1. // #define INTERACTIVE
  2. #include <vector>
  3. #include <iostream>
  4. #include <chrono>
  5. #include <random>
  6. #include <deque>
  7. #include <set>
  8. #include <map>
  9. #include <iomanip>
  10. #include <fstream>
  11. #include <queue>
  12. #include <algorithm>
  13. using namespace std;
  14. typedef long long ll;
  15. typedef unsigned long long ull;
  16. typedef long double ld;
  17. typedef pair<int, int> pii;
  18. typedef pair<ll, ll> pll;
  19. typedef pair<double, double> pdd;
  20. //template <typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
  21. //template <typename T> using max_heap = priority_queue<T, vector<T>, less<T>>;
  22.  
  23. template<typename A, typename B> ostream& operator<<(ostream& out, pair<A, B> p) { out << "(" << p.first << ", " << p.second << ")"; return out; }
  24. template<typename T> ostream& operator<<(ostream& out, vector<T> v) { out << "["; for (auto& x : v) out << x << ", "; out << "]"; return out; }
  25. template<typename T> ostream& operator<<(ostream& out, deque<T> v) { out << "["; for (auto& x : v) out << x << ", "; out << "]"; return out; }
  26. template<typename T> ostream& operator<<(ostream& out, set<T> v) { out << "{"; for (auto& x : v) out << x << ", "; out << "}"; return out; }
  27. template<typename K, typename V> ostream& operator<<(ostream& out, map<K, V> m) { out << "{"; for (auto& e : m) out << e.first << " -> " << e.second << ", "; out << "}"; return out; }
  28.  
  29. template<typename T> T read() { T x; cin >> x; return x; }
  30. template<typename T> vector<T> read(int n) { vector<T> v(n); for (auto& x : v) cin >> x; return v; }
  31. template<typename A, typename B>istream& operator>>(istream& in, pair<A, B>& p) { return in >> p.first >> p.second; }
  32.  
  33. #define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr)
  34. #define TESTS(t) int NUMBER_OF_TESTS; cin >> NUMBER_OF_TESTS; for(int t = 1; t <= NUMBER_OF_TESTS; t++)
  35. #define FOR(i, begin, end) for (int i = (begin); i < (end); i++)
  36. #define sgn(a)     ((a) > eps ? 1 : ((a) < -eps ? -1 : 0))
  37. #define precise(x) fixed << setprecision(x)
  38. #define all(a) a.begin(), a.end()
  39. #define pb push_back
  40. #define rnd(a, b) (uniform_int_distribution<int>((a), (b))(rng))
  41. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  42. std::chrono::steady_clock::time_point __clock__;
  43. void startTime() { __clock__ = std::chrono::steady_clock::now(); }
  44. ld getTime() {
  45.     auto end = std::chrono::steady_clock::now();
  46.     auto t = std::chrono::duration_cast<std::chrono::microseconds> (end - __clock__).count();
  47.     return ld(t) / 1e6;
  48. }
  49. void timeit(string msg) {
  50.     cerr << "> " << msg << ": " << precise(6) << getTime() << endl;
  51. }
  52. template<typename T> inline bool maxi(T& a, T b) { return b > a ? (a = b, true) : false; }
  53. template<typename T> inline bool mini(T& a, T b) { return b < a ? (a = b, true) : false; }
  54. const ld PI = asin(1) * 2;
  55. const ld eps = 1e-6;
  56. const int oo = 2e9;
  57. const ll OO = 2e18;
  58. const ll MOD = 1000000007;
  59. const int MAXN = 200000;
  60.  
  61. struct library {
  62.     int id;
  63.     int signupTime;
  64.     int scansPerDay;
  65.     vector<int> bookIds;
  66. };
  67.  
  68. ostream& operator<<(ostream& out, const library& lib) {
  69.     return out << "(t=" << lib.signupTime << ", m=" << lib.scansPerDay << ", bookIds=" << lib.bookIds << ")";
  70. }
  71.  
  72. vector<int> bookValues;
  73. vector<library> libraries;
  74. int numDays;
  75.  
  76. map<char, int> bestScores;
  77. void initScores() {
  78.     bestScores['a'] = 21;
  79.     bestScores['b'] = 5822900;
  80.     bestScores['c'] = 5689822;
  81.     bestScores['d'] = 5040490;
  82.     bestScores['e'] = 5192117;
  83.     bestScores['f'] = 5317473;
  84. }
  85.  
  86. void reset() {
  87.     bookValues.clear();
  88.     libraries.clear();
  89.     numDays = 0;
  90. }
  91.  
  92. void readInput(string inFile) {
  93.     ifstream in(inFile);
  94.     int b, l;
  95.     in >> b >> l >> numDays;
  96.     bookValues.resize(b);
  97.     for (auto& x : bookValues) in >> x;
  98.     libraries.resize(l);
  99.     int id = 0;
  100.     for (auto& lib : libraries) {
  101.         int n;
  102.         lib.id = id;
  103.         in >> n >> lib.signupTime >> lib.scansPerDay;
  104.         lib.bookIds.resize(n);
  105.         for (auto& i : lib.bookIds) {
  106.             in >> i;
  107.         }
  108.         id++;
  109.     }
  110. }
  111.  
  112. queue<int> toQueue(vector<int> v) {
  113.     queue<int> Q;
  114.     for (auto x : v) Q.push(x);
  115.     return Q;
  116. }
  117.  
  118. int calcScore() {
  119.     int score = 0;
  120.     int timeLeft = numDays;
  121.     vector<bool> isTaken(bookValues.size());
  122.     for (auto& lib : libraries) {
  123.         timeLeft -= lib.signupTime;
  124.         if (timeLeft <= 0) break;
  125.         int bookLimit = timeLeft * lib.scansPerDay;
  126.         for (auto& bookId : lib.bookIds) {
  127.             if (bookLimit-- == 0) break;
  128.             isTaken[bookId] = true;
  129.         }
  130.     }
  131.     FOR(i, 0, (int)bookValues.size()) {
  132.         if (isTaken[i]) score += bookValues[i];
  133.     }
  134.  
  135.     return score;
  136. }
  137.  
  138. void dumpOutput(string problemId) {
  139.     ofstream out("output_" + problemId + ".txt");
  140.     out << libraries.size() << endl;
  141.     for (auto& lib : libraries) {
  142.         out << lib.id << " " << lib.bookIds.size() << endl;
  143.         for (auto book : lib.bookIds) {
  144.             out << book << " ";
  145.         }
  146.         out << endl;
  147.     }
  148. }
  149.  
  150.  
  151. namespace sortBySignup {
  152.     bool cmpLib(const library& a, const library& b) {
  153.         return a.signupTime < b.signupTime;
  154.     }
  155.  
  156.     void optimize() {
  157.         sort(libraries.begin(), libraries.end(), cmpLib);
  158.         cerr << "sorted by signup time" << endl;
  159.     }
  160. }
  161.  
  162. namespace sortByValuePerTime {
  163.     vector<int> libValue;
  164.     vector<vector<int>> parentLib;
  165.     vector<int> bookVal;
  166.  
  167.     library pickLib() {
  168.         int bestIndex = -1;
  169.         double bestScore = -1;
  170.         for (int i = 0; i < (int)libraries.size(); i++) {
  171.             if (libValue[libraries[i].id] < 0)
  172.                 continue;
  173.             double score = (double)libValue[libraries[i].id] / (double)libraries[i].signupTime;
  174.             if (score > bestScore) {
  175.                 bestScore = score;
  176.                 bestIndex = i;
  177.             }
  178.         }
  179.         auto lib = libraries[bestIndex];
  180.         libValue[lib.id] = -1;
  181.         return lib;
  182.     }
  183.  
  184.     void optimize() {
  185.         bookVal = bookValues;
  186.         libValue.resize(0);
  187.         libValue.resize(libraries.size());
  188.         parentLib.clear();
  189.         parentLib.resize(bookValues.size());
  190.  
  191.         for (auto& lib : libraries) {
  192.             int total = 0;
  193.             for (auto book : lib.bookIds) {
  194.                 total += bookVal[book];
  195.                 parentLib[book].push_back(lib.id);
  196.             }
  197.             libValue[lib.id] = total;
  198.         }
  199.  
  200.         vector<library> newOrder;
  201.         for (int i = 0; i < (int)libraries.size(); i++) {
  202.             auto lib = pickLib();
  203.             for (auto book : lib.bookIds) {
  204.                 if (bookVal[book] == -1)
  205.                     continue;
  206.                 auto val = bookVal[book];
  207.                 bookVal[book] = -1;
  208.                 for (auto pl : parentLib[book]) {
  209.                     libValue[pl] -= val;
  210.                 }
  211.             }
  212.  
  213.             newOrder.push_back(lib);
  214.         }
  215.  
  216.         libraries = newOrder;
  217.  
  218.         cerr << "sorted by value per time" << endl;
  219.     }
  220. }
  221.  
  222. namespace sortBooksByValue {
  223.     bool cmpBook(const int& a, const int& b) {
  224.         return bookValues[a] > bookValues[b];
  225.     }
  226.  
  227.     void optimize() {
  228.         for (auto& lib : libraries) {
  229.             sort(lib.bookIds.begin(), lib.bookIds.end(), cmpBook);
  230.         }
  231.         cerr << "sorted books by value" << endl;
  232.     }
  233. }
  234.  
  235. namespace simulateAndSkipBooks {
  236.  
  237.     void optimize() {
  238.         set<int> usedBookIds;
  239.         int currentLib = 0;
  240.         int queueTimeLeft = 0;
  241.         vector<queue<int>> queues(libraries.size());
  242.         vector<vector<int>> takenBooks(libraries.size());
  243.         vector<vector<int>> skippedBooks(libraries.size());
  244.         for (int day = 0; day < numDays; day++, queueTimeLeft--) {
  245.             if (queueTimeLeft <= 0 && currentLib + 1 < (int)libraries.size()) {
  246.                 // enqueue new
  247.                 queues[currentLib] = toQueue(libraries[currentLib].bookIds);
  248.                 queueTimeLeft = libraries[currentLib].signupTime;
  249.                 currentLib++;
  250.             }
  251.             // process queues
  252.             for (int i = (int)queues.size() - 1; i >= 0; i--) {
  253.                 // FOR(i, 0, (int)queues.size()) {
  254.                 auto& lib = libraries[i];
  255.                 FOR(_, 0, lib.scansPerDay) {
  256.                     if (queues[i].empty()) break;
  257.                     int bookId = queues[i].front(); queues[i].pop();
  258.                     if (usedBookIds.count(bookId) > 0) {
  259.                         // somehow skip this biatch
  260.                         skippedBooks[i].pb(bookId);
  261.                         _--;
  262.                     } else {
  263.                         takenBooks[i].pb(bookId);
  264.                         usedBookIds.insert(bookId);
  265.                     }
  266.                 }
  267.             }
  268.         }
  269.         FOR(i, currentLib, (int)libraries.size()) {
  270.             queues[i] = toQueue(libraries[i].bookIds);
  271.         }
  272.         FOR(i, 0, (int)queues.size()) {
  273.             while (!queues[i].empty()) {
  274.                 skippedBooks[i].pb(queues[i].front());
  275.                 queues[i].pop();
  276.             }
  277.         }
  278.         vector<library> newLibs;
  279.         FOR(i, 0, (int)libraries.size()) {
  280.             library l;
  281.             l.id = libraries[i].id;
  282.             l.scansPerDay = libraries[i].scansPerDay;
  283.             l.signupTime = libraries[i].signupTime;
  284.             for (auto x : takenBooks[i]) l.bookIds.pb(x);
  285.             for (auto x : skippedBooks[i]) l.bookIds.pb(x);
  286.             if (l.bookIds.size() > 0) newLibs.pb(l);
  287.         }
  288.         libraries = newLibs;
  289.     }
  290. }
  291.  
  292.  
  293. namespace sortByValuePerTime2 {
  294.     vector<bool> isTaken;
  295.  
  296.     library pickLibrary(int timeLeft) {
  297.         int bestIndex = 0;
  298.         double bestScore = -1;
  299.         for (int i = 0; i < libraries.size(); i++) {
  300.             if (libraries[i].signupTime >= timeLeft)
  301.                 continue;
  302.             int bookLimit = timeLeft * libraries[i].scansPerDay;
  303.             int libScore = 0;
  304.             for (auto book : libraries[i].bookIds) {
  305.                 if (isTaken[book])
  306.                     continue;
  307.                 libScore += bookValues[book];
  308.                 bookLimit -= 1;
  309.                 if (bookLimit <= 0)
  310.                     break;
  311.             }
  312.             double score = (double)libScore / (double)libraries[i].signupTime;
  313.             if (score > bestScore) {
  314.                 bestIndex = i;
  315.                 bestScore = score;
  316.             }
  317.         }
  318.  
  319.         auto x = libraries[bestIndex];
  320.         libraries[bestIndex] = libraries[libraries.size() - 1];
  321.         libraries.pop_back();
  322.         return x;
  323.     }
  324.  
  325.     void optimize() {
  326.         isTaken.clear();
  327.         isTaken.resize(bookValues.size());
  328.  
  329.         vector<library> newOrder;
  330.         int timeLeft = numDays;
  331.         while (libraries.size() > 0) {
  332.             auto lib = pickLibrary(timeLeft);
  333.             timeLeft -= lib.signupTime;
  334.             newOrder.push_back(lib);
  335.             int bookLimit = timeLeft * lib.scansPerDay;
  336.             for (auto book : lib.bookIds) {
  337.                 if (isTaken[book])
  338.                     continue;
  339.                 isTaken[book] = true;
  340.                 bookLimit--;
  341.                 if (bookLimit <= 0)
  342.                     break;
  343.             }
  344.         }
  345.  
  346.         libraries = newOrder;
  347.         cerr << "sorted by value per time (2)" << endl;
  348.     }
  349. }
  350.  
  351. namespace sortBooksBySomethingArbitrary {
  352.     vector<bool> isTaken;
  353.     vector<bool> isLibraryComplete;
  354.  
  355.     void optimize() {
  356.         isTaken.clear();
  357.         isTaken.resize(bookValues.size());
  358.         isLibraryComplete.clear();
  359.         isLibraryComplete.resize(libraries.size());
  360.         while (true) {
  361.             bool completedAny = false;
  362.             int timeLeft = numDays;
  363.             for (int i = 0; i < libraries.size(); i++) {
  364.                 timeLeft -= libraries[i].signupTime;
  365.                 if (isLibraryComplete[i])
  366.                     continue;
  367.                 int booksTaken = 0;
  368.                 for (auto book : libraries[i].bookIds)
  369.                     if (!isTaken[book])
  370.                         booksTaken++;
  371.                 if (booksTaken <= timeLeft * libraries[i].scansPerDay) {
  372.                     isLibraryComplete[i] = true;
  373.                     for (auto book : libraries[i].bookIds)
  374.                         isTaken[book] = true;
  375.                     completedAny = true;
  376.                 }
  377.             }
  378.             if (!completedAny)
  379.                 break;
  380.         }
  381.  
  382.         int timeLeft = numDays;
  383.         for (int i = 0; i < libraries.size(); i++) {
  384.             timeLeft -= libraries[i].signupTime;
  385.             if (isLibraryComplete[i])
  386.                 continue;
  387.  
  388.             vector<int> take;
  389.             vector<int> notTake;
  390.             int bookLimit = timeLeft * libraries[i].scansPerDay;
  391.             for (auto book : libraries[i].bookIds) {
  392.                 if (bookLimit <= 0 || isTaken[book]) {
  393.                     notTake.push_back(book);
  394.                 } else {
  395.                     isTaken[book] = true;
  396.                     take.push_back(book);
  397.                     bookLimit--;
  398.                 }
  399.             }
  400.             libraries[i].bookIds.clear();
  401.             for (auto x : take) libraries[i].bookIds.push_back(x);
  402.             for (auto x : notTake) libraries[i].bookIds.push_back(x);
  403.         }
  404.  
  405.         cerr << "finished sorting books by something arbitrary" << endl;
  406.     }
  407. }
  408.  
  409. namespace tryToFixLastLibrary {
  410.     void optimize(string problemId, int requiredDiff) {
  411.         int score = calcScore();
  412.         int bestScore = bestScores[problemId[0]];
  413.         cout << "currently behind " << score - bestScore << endl;
  414.         int steps = libraries.size() * (libraries.size() - 1) / 2;
  415.         FOR(i, 0, (int)libraries.size()) {
  416.             FOR(j, i + 1, (int)libraries.size()) {
  417.                 steps--;
  418.                 if (steps % 20000 == 0) {
  419.                     cout << "steps remaining: " << steps << endl;
  420.                 }
  421.                 swap(libraries[i], libraries[j]);
  422.                 int newScore = calcScore();
  423.                 if (newScore > score + requiredDiff) {
  424.                     cout << "got extra " << newScore - score << endl;
  425.                     score = newScore;
  426.                     cout << "still behind " << bestScore - score << endl;
  427.                     if (score > bestScore) dumpOutput(problemId);
  428.                 } else {
  429.                     swap(libraries[i], libraries[j]);
  430.                 }
  431.             }
  432.         }
  433.         // if (bestI != -1 && bestJ != -1) {
  434.         //     swap(libraries[bestI], libraries[bestJ]);
  435.         // }
  436.     }
  437. }
  438.  
  439. namespace sortLibrariesWell {
  440.     vector<bool> isTaken;
  441.     vector<int> bookRep;
  442.  
  443.     library pickLibrary(int timeLeft) {
  444.         int bestIndex = 0;
  445.         double bestScore = -1;
  446.         for (int i = 0; i < libraries.size(); i++) {
  447.             if (libraries[i].signupTime >= timeLeft)
  448.                 continue;
  449.             int bookLimit = timeLeft * libraries[i].scansPerDay;
  450.             double libScore = 0;
  451.             for (auto book : libraries[i].bookIds) {
  452.                 if (isTaken[book])
  453.                     continue;
  454.                 libScore += bookValues[book] / sqrt(sqrt((double)bookRep[book]));
  455.                 bookLimit -= 1;
  456.                 if (bookLimit <= 0)
  457.                     break;
  458.             }
  459.             double score = (double)libScore / (double)libraries[i].signupTime;
  460.             if (score > bestScore) {
  461.                 bestIndex = i;
  462.                 bestScore = score;
  463.             }
  464.         }
  465.  
  466.         auto x = libraries[bestIndex];
  467.         libraries[bestIndex] = libraries[libraries.size() - 1];
  468.         libraries.pop_back();
  469.         return x;
  470.     }
  471.  
  472.     void optimize() {
  473.         isTaken.clear();
  474.         isTaken.resize(bookValues.size());
  475.         bookRep.clear();
  476.         bookRep.resize(bookValues.size());
  477.  
  478.         for (auto& lib : libraries) {
  479.             for (auto book : lib.bookIds) {
  480.                 bookRep[book]++;
  481.             }
  482.         }
  483.  
  484.         vector<library> newOrder;
  485.         int timeLeft = numDays;
  486.         while (libraries.size() > 0) {
  487.             auto lib = pickLibrary(timeLeft);
  488.             timeLeft -= lib.signupTime;
  489.             newOrder.push_back(lib);
  490.             int bookLimit = timeLeft * lib.scansPerDay;
  491.             for (auto book : lib.bookIds) {
  492.                 if (isTaken[book])
  493.                     continue;
  494.                 bookRep[book] -= 1;
  495.                 isTaken[book] = true;
  496.                 bookLimit--;
  497.                 if (bookLimit <= 0)
  498.                     break;
  499.             }
  500.         }
  501.  
  502.         libraries = newOrder;
  503.         cerr << "sorted libraries well" << endl;
  504.     }
  505. }
  506.  
  507. void solve(string problemId) {
  508.     initScores();
  509.     readInput("inputs/" + problemId + ".txt");
  510.  
  511.     sortByValuePerTime::optimize();
  512.     //sortBySignup::optimize();
  513.     sortBooksByValue::optimize();
  514.     if (problemId[0] == 'd' || problemId[0] == 'e') {
  515.         sortLibrariesWell::optimize();
  516.     } else {
  517.         sortByValuePerTime2::optimize();
  518.     }
  519.     simulateAndSkipBooks::optimize();
  520.     sortBooksBySomethingArbitrary::optimize();
  521.     tryToFixLastLibrary::optimize(problemId, 100);
  522.     simulateAndSkipBooks::optimize();
  523.     tryToFixLastLibrary::optimize(problemId, 0);
  524.     for (;;) {
  525.         simulateAndSkipBooks::optimize();
  526.         tryToFixLastLibrary::optimize(problemId, 0);
  527.     }
  528.     cout << "\t\t\t\t\t" << problemId[0] << " score: " << calcScore() << " (diff: " << calcScore() - bestScores[problemId[0]] << ")" << endl;
  529.     if (calcScore() > bestScores[problemId[0]]) {
  530.         cout << "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAmazing" << endl;
  531.     }
  532.  
  533.     dumpOutput(problemId);
  534.     cerr << "finished " << problemId << endl;
  535. }
  536.  
  537. int main() {
  538.     FAST_IO;
  539.     startTime();
  540.  
  541.     // solve("a_example");
  542.     // solve("b_read_on");
  543.     //solve("c_incunabula");
  544.     // solve("d_tough_choices");
  545.     solve("e_so_many_books");
  546.     //solve("f_libraries_of_the_world");
  547.  
  548.     timeit("Finished");
  549.     return 0;
  550. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!