SHARE
TWEET

Untitled

a guest Jan 21st, 2016 1,091 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define forn(i, n) for (int i = 0; i < int(n); i++)
  4. #define ford(i, n) for (int i = int(n) - 1; i >= 0; i--)
  5. #define fore(i, l, r) for (int i = int(l); i < int(r); i++)
  6. #define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
  7. #define all(a) (a).begin(), (a).end()
  8. #define sz(a) int((a).size())
  9. #define pb(a) push_back(a)
  10. #define mp(x, y) make_pair((x), (y))
  11. #define x first
  12. #define y second
  13.  
  14. using namespace std;
  15.  
  16. typedef long long li;
  17. typedef long double ld;
  18. typedef pair<int, int> pt;
  19.  
  20. template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
  21. template<typename X> inline X sqr(const X& a) { return a * a; }
  22.  
  23. const int INF = int(1e9);
  24. const li INF64 = li(1e18);
  25. const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;
  26.  
  27. const int N = 2020;
  28.  
  29. int n, a[N];
  30. int m, b[N];
  31.  
  32. inline bool read() {
  33.     if (!(cin >> n)) return false;
  34.     forn(i, n) assert(scanf("%d", &a[i]) == 1);
  35.     assert(cin >> m);
  36.     forn(i, m) assert(scanf("%d", &b[i]) == 1);
  37.     return true;
  38. }
  39.  
  40. li sa, sb;
  41.  
  42. inline void solve() {
  43.     sa = accumulate(a, a + n, 0ll);
  44.     sb = accumulate(b, b + m, 0ll);
  45.  
  46.     li ansv = INF64;
  47.     vector<pt> ansp;
  48.  
  49.     {
  50.         li curv = abs(sa - sb);
  51.         if (ansv > curv) {
  52.             ansv = curv;
  53.             ansp.clear();
  54.         }
  55.     }
  56.  
  57.     forn(i, n)
  58.         forn(j, m) {
  59.             sa += b[j] - a[i];
  60.             sb += a[i] - b[j];
  61.             li curv = abs(sa - sb);
  62.             if (ansv > curv) {
  63.                 ansv = curv;
  64.                 ansp.clear();
  65.                 ansp.pb(mp(i, j));
  66.             }
  67.             sa -= b[j] - a[i];
  68.             sb -= a[i] - b[j];
  69.         }
  70.  
  71.     map<li, pt> z;
  72.     forn(j, n)
  73.         forn(i, j)
  74.             z[2ll * (a[i] + a[j])] = mp(i, j);
  75.  
  76.     forn(j, m)
  77.         forn(i, j) {
  78.             li val = sa - sb + 2ll * (b[i] + b[j]);
  79.             auto it = z.lower_bound(val);
  80.             if (it != z.begin()) it--;
  81.             forn(k, 2) {
  82.                 if (it == z.end()) break;
  83.                 li curv = abs(val - it->x);
  84.                 pt p = it->y;
  85.                 assert(abs(sa - 2ll * (a[p.x] + a[p.y]) - (sb - 2ll * (b[i] + b[j]))) == curv);
  86.                 if (ansv > curv) {
  87.                     ansv = curv;
  88.                     ansp.clear();
  89.                     ansp.pb(mp(p.x, i));
  90.                     ansp.pb(mp(p.y, j));
  91.                 }
  92.                 it++;
  93.             }
  94.         }
  95.  
  96.     assert(ansv != INF64);
  97.     cout << ansv << endl;
  98.     cout << sz(ansp) << endl;
  99.     forn(i, sz(ansp)) cout << ansp[i].x + 1 << ' ' << ansp[i].y + 1 << endl;
  100. }
  101.  
  102. int main() {
  103. #ifdef SU1
  104.     assert(freopen("input.txt", "rt", stdin));
  105.     //assert(freopen("output.txt", "wt", stdout));
  106. #endif
  107.    
  108.     cout << setprecision(10) << fixed;
  109.     cerr << setprecision(5) << fixed;
  110.  
  111.     while (read()) {
  112.         solve();
  113.         //break;
  114.     }
  115.    
  116.     return 0;
  117. }
RAW Paste Data
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
 
Top