Advertisement
Guest User

Untitled

a guest
Sep 21st, 2013
167
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.68 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <set>
  7.  
  8. using namespace std;
  9.  
  10. #define x first
  11. #define y second
  12. #define mp make_pair
  13. #define pb push_back
  14.  
  15. typedef pair <int, int> pii;
  16. typedef pair <int, pii> pkk;
  17.  
  18. const int N = 1e5 + 5;
  19.  
  20. int n, m, k;
  21.  
  22. set <int> v[N];
  23. int u[N];
  24.  
  25. pii d[N];
  26.  
  27. int main()
  28. {
  29.     freopen("towers.in", "r", stdin);
  30.     freopen("towers.out", "w", stdout);
  31.  
  32.     cin >> n >> m >> k;
  33.  
  34.     for (int i = 0; i < k; i++)
  35.     {
  36.       int x, y;
  37.       scanf("%d%d", &x, &y);
  38.       x--; y--;
  39.       v[x].insert(y);
  40.     }
  41.  
  42.     cin >> k;
  43.     for (int i = 0; i < k; i++)
  44.     {
  45.       int a, b, c, d1;
  46.       scanf("%d%d%d%d", &a, &b, &c, &d1);
  47.  
  48.       u[0] = a;
  49.       for (int j = 1; j < n; j++)
  50.         u[j] = (1LL * u[j - 1] * b + c) % d1;
  51.       d[0] = mp((1LL * u[n - 1] * b + c) % d1, 0);
  52.       for (int j = 1; j < m; j++)
  53.         d[j] = mp((1LL * d[j - 1].x * b + c) % d1, j);
  54.  
  55.       /*for (int j = 0; j < n; j++)
  56.         cout << u[j] << " ";
  57.       cout << endl;
  58.       for (int j = 0; j < m; j++)
  59.         cout << d[j].x << " ";
  60.       cout << endl;*/
  61.  
  62.       sort(d, d + m);
  63.       pkk ans = mp(-1, mp(-1, -1));
  64.       for (int j = 0; j < n; j++)
  65.       {
  66.         for (int z = m - 1; z >= 0; z--)
  67.           if (v[j].find(d[z].y) == v[j].end())
  68.           {
  69.             if (ans.x < (u[j] + d[z].x))
  70.               ans = mp(u[j] + d[z].x, mp(j, d[z].y));
  71.             break;
  72.           }
  73.       }
  74.  
  75.       if (ans.x == -1) cout << -1 << endl;
  76.       else cout << ans.y.x + 1 << " " << ans.y.y + 1 << endl;
  77.     }
  78.  
  79.     return 0;
  80. }
  81.  
  82. /*
  83. 4 5 3
  84. 1 2
  85. 1 3
  86. 4 5
  87. 1
  88. 7 2 4 199
  89. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement