Guest User

Auction solution

a guest
Jan 24th, 2012
444
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cassert>
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <utility>
  5. #include <vector>
  6. using namespace std;
  7.  
  8. typedef long long LL;
  9. typedef vector<int> VI;
  10.  
  11. struct PriceWeights
  12. {
  13.     int price, min_weight, max_weight;
  14.     LL min_count, max_count;
  15.  
  16.     bool operator< (const PriceWeights &o) const { return price < o.price; }
  17. };
  18.  
  19. struct TreeNode
  20. {
  21.     TreeNode(size_t i, TreeNode *l = 0, TreeNode *r = 0)
  22.         : left(l), right(r), index(i) { }
  23.     ~TreeNode() { delete left; delete right; }
  24.  
  25.     TreeNode * const left, * const right;
  26.     const size_t index;
  27. };
  28.  
  29. template<class Comp>
  30. struct MinTree
  31. {
  32.     MinTree(Comp c, VI &v)
  33.         : comp(c), values(v), nodes(create_node(0, v.size())) { };
  34.     size_t find_min_index(size_t start, size_t length) const;
  35.     ~MinTree() { delete nodes; }
  36.  
  37. private:
  38.     Comp comp;
  39.     VI &values;
  40.     TreeNode *nodes;
  41.  
  42.     TreeNode *create_node(size_t begin, size_t end);
  43.     size_t find_min_index( const TreeNode *node,
  44.                            size_t node_begin, size_t node_end,
  45.                            size_t range_begin, size_t range_end ) const;
  46.     size_t min_index(size_t i, size_t j) const {
  47.         return comp(values[i], values[j]) ? i : j;
  48.     }
  49. };
  50.  
  51. template<class Comp>
  52. TreeNode *MinTree<Comp>::create_node(size_t begin, size_t end)
  53. {
  54.     if (end - begin == 1) return new TreeNode(begin);
  55.     size_t middle = (begin + end)/2;
  56.     TreeNode *left  = create_node(begin, middle),
  57.              *right = create_node(middle, end);
  58.     return new TreeNode(min_index(left->index, right->index), left, right);
  59. }
  60.  
  61. template<class Comp>
  62. size_t MinTree<Comp>::find_min_index( const TreeNode *node,
  63.                                       size_t node_begin, size_t node_end,
  64.                                       size_t range_begin, size_t range_end ) const
  65. {
  66.     if (range_begin <= node_begin && range_end >= node_end)
  67.         return node->index;
  68.     size_t middle = (node_begin + node_end)/2;
  69.     if (range_end <= middle)
  70.         return find_min_index(node->left, node_begin, middle, range_begin, range_end);
  71.     if (range_begin >= middle)
  72.         return find_min_index(node->right, middle, node_end, range_begin, range_end);
  73.     return min_index( find_min_index(node->left, node_begin, middle, range_begin, middle),
  74.                       find_min_index(node->right, middle, node_end, middle, range_end) );
  75. }
  76.  
  77. template<class Comp>
  78. size_t MinTree<Comp>::find_min_index(size_t begin, size_t length) const
  79. {
  80.     size_t n = values.size();
  81.     if (length >= n) {
  82.         return nodes->index;
  83.     }
  84.     size_t end = begin + length;
  85.     if (end <= n) {
  86.         return find_min_index(nodes, 0, n, begin, end);
  87.     } else {
  88.         return min_index( find_min_index(nodes, 0, n, begin, n),
  89.                           find_min_index(nodes, 0, n, 0, end - n) );
  90.     }
  91. }
  92.  
  93. static void gen_sequence(VI &v, int P1, int M, int A, int B)
  94. {
  95.     assert(0 < P1 && P1 <= M);
  96.     v.clear();
  97.     v.reserve(M);
  98.     int x = P1;
  99.     do {
  100.         v.push_back(x);
  101.         x = ((LL)A*x + B)%M + 1;
  102.     } while (x != P1);
  103. }
  104.  
  105. static LL num_solutions(LL i, LL P, LL N)
  106. {
  107.     assert(0 <= i && i < N && i < P);
  108.     return (N - (i + 1))/P + 1;
  109. }
  110.  
  111. static void generate_price_weights( vector<PriceWeights> &pws,
  112.                                     LL N, const VI &P, const VI &W )
  113. {
  114.     pws.reserve(min((LL)P.size(), N));
  115.  
  116.     LL NP = P.size();
  117.     LL NW = W.size();
  118.     int K = __gcd(NP, NW);
  119.     LL L = (LL)NP/K*NW;
  120.  
  121.     LL NV = NW/K;
  122.     vector<int> V(NV);
  123.     for (LL k = 0; k < K; ++k)
  124.     {
  125.         int step = K;
  126.         for (LL i = 0; i < NV; ++i) {
  127.             int j = (k + NP*i)%NW;
  128.             V[i] = W[j];
  129.             if (NP*i%NW == K) step = i;
  130.         }
  131.         MinTree<less<int> > min_tree(less<int>(), V);
  132.         MinTree<greater<int> > max_tree(greater<int>(), V);
  133.         for (LL i = k; i < min(N, NP); i += K) {
  134.             LL n = num_solutions(i, NP, N);
  135.             LL min_j = min_tree.find_min_index(i/K*step%NV, n);
  136.             LL max_j = max_tree.find_min_index(i/K*step%NV, n);
  137.             PriceWeights pw = { P[i], V[min_j], V[max_j],
  138.                 num_solutions(i + ((min_j - i/K*step)%NV + NV)%NV*NP, L, N),
  139.                 num_solutions(i + ((max_j - i/K*step)%NV + NV)%NV*NP, L, N) };
  140.             pws.push_back(pw);
  141.         }
  142.     }
  143. }
  144.  
  145. static void merge( vector<PriceWeights> &c,
  146.                    const vector<PriceWeights> &a,
  147.                    const vector<PriceWeights> &b )
  148. {
  149.     vector<PriceWeights>::const_iterator i = a.begin(), j = b.begin();
  150.     while (i != a.end() && j != b.end())
  151.     {
  152.         if (i->price < j->price) {
  153.             c.push_back(*i++);
  154.         } else if (j->price < i->price) {
  155.             c.push_back(*j++);
  156.         } else {
  157.             PriceWeights pw = { i->price,
  158.                 min(i->min_weight, j->min_weight),
  159.                 max(i->max_weight, j->max_weight), 0, 0 };
  160.             if (pw.min_weight == i->min_weight) pw.min_count += i->min_count;
  161.             if (pw.min_weight == j->min_weight) pw.min_count += j->min_count;
  162.             if (pw.max_weight == i->max_weight) pw.max_count += i->max_count;
  163.             if (pw.max_weight == j->max_weight) pw.max_count += j->max_count;
  164.             c.push_back(pw);
  165.             ++i, ++j;
  166.         }
  167.     }
  168.     c.insert(c.end(), i, a.end());
  169.     c.insert(c.end(), j, b.end());
  170. }
  171.  
  172. static void aggregate(vector<PriceWeights> &pws, vector<pair<int, int> > &pairs)
  173. {
  174.     sort(pairs.begin(), pairs.end());
  175.     size_t i = 0;
  176.     while (i < pairs.size()) {
  177.         PriceWeights pw = { pairs[i].first, pairs[i].second, pairs[i].second, 1, 1 };
  178.         size_t j = i + 1;
  179.         while (j < pairs.size() && pairs[i].first == pairs[j].first) {
  180.             int weight = pairs[j].second;
  181.             if (weight < pw.min_weight) pw.min_weight = weight, pw.min_count  = 0;
  182.             if (weight > pw.max_weight) pw.max_weight = weight, pw.max_count  = 0;
  183.             if (weight == pw.min_weight) ++pw.min_count;
  184.             if (weight == pw.max_weight) ++pw.max_count;
  185.             ++j;
  186.         }
  187.         pws.push_back(pw);
  188.         i = j;
  189.     }
  190. }
  191.  
  192. static pair<LL,LL> solve(LL N, int P1, int W1, int M, int K, int A, int B, int C, int D)
  193. {
  194.     vector<PriceWeights> pws;
  195.     int peel = (int)min(N, (LL)max(M, K));
  196.     {
  197.         vector<pair<int, int> > pairs;
  198.         for (int p = 0; p < peel; ++p)
  199.         {
  200.             pairs.push_back(make_pair(P1, W1));
  201.             P1 = ((LL)A*P1 + B)%M + 1;
  202.             W1 = ((LL)C*W1 + D)%K + 1;
  203.         }
  204.         aggregate(pws, pairs);
  205.     }
  206.     if (peel < N) {
  207.         vector<PriceWeights> pws2;
  208.         vector<int> P, W;
  209.         gen_sequence(P, P1, M, A, B);
  210.         gen_sequence(W, W1, K, C, D);
  211.         generate_price_weights(pws2, N - peel, P, W);
  212.         sort(pws2.begin(), pws2.end());
  213.  
  214.         vector<PriceWeights> pws_merged;
  215.         merge(pws_merged, pws, pws2);
  216.         pws.swap(pws_merged);
  217.     }
  218.  
  219.     pair<LL,LL> answer(0, 0);
  220.     int last_weight = -1;
  221.     for (vector<PriceWeights>::const_iterator it = pws.begin();
  222.          it != pws.end(); ++it)
  223.     {
  224.         if (last_weight == -1 || it->min_weight < last_weight) {
  225.             last_weight = it->min_weight;
  226.             answer.second += it->min_count;
  227.         }
  228.     }
  229.     last_weight = -1;
  230.     for (vector<PriceWeights>::const_reverse_iterator it = pws.rbegin();
  231.          it != pws.rend(); ++it)
  232.     {
  233.         if (last_weight == -1 || it->max_weight > last_weight) {
  234.             last_weight = it->max_weight;
  235.             answer.first+= it->max_count;
  236.         }
  237.     }
  238.     return answer;
  239. }
  240.  
  241. int main()
  242. {
  243.     int T = 0;
  244.     cin >> T;
  245.     for (int t = 1; t <= T; ++t) {
  246.         LL N;
  247.         int P1, W1, M, K, A, B, C, D;
  248.         if (!(cin >> N >> P1 >> W1 >> M >> K >> A >> B >> C >> D)) {
  249.             std::cerr << "Failed to read case #" << t << "!\n";
  250.             return 1;
  251.         } else {
  252.             pair<LL,LL> answer = solve(N, P1, W1, M, K, A, B, C, D);
  253.             std::cout << "Case #" << t << ": "
  254.                       << answer.first << ' ' << answer.second << '\n';
  255.         }
  256.     }
  257. }
RAW Paste Data