Malinovsky239

Untitled

Sep 25th, 2012
444
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <deque>
  6. #include <queue>
  7. #include <bitset>
  8. #include <sstream>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <numeric>
  12. #include <iostream>
  13. #include <cstdio>
  14. #include <cmath>
  15. #include <cstdlib>
  16. #include <ctime>
  17. #include <cstring>
  18. #include <cassert>
  19.  
  20. using namespace std;
  21.  
  22. #define forn(i, n) for(int i = 0; i < int(n); ++i)
  23. #define for1(i, n) for(int i = 1; i <= int(n); ++i)
  24. #define ford(i, n) for(int i = int(n) - 1; i >= 0; --i)
  25. #define fore(i, l, r) for(int i = int(l); i < int(r); ++i)
  26. #define sz(v) int((v).size())
  27. #define all(v) (v).begin(), (v).end()
  28. #define pb push_back
  29. #define X first
  30. #define Y second
  31. #define mp make_pair
  32. #define debug(x) {cerr << #x << " = " << x << endl;}
  33. template<typename T> inline T abs(T a){ return ((a < 0) ? -a : a); }
  34. template<typename T> inline T sqr(T a){ return a * a; }
  35.  
  36. typedef long long li;
  37. typedef long double ld;
  38. typedef pair<int, int> pt;
  39.  
  40. const int INF = (int)1E9 + 7;
  41. const ld EPS = 1E-9;
  42. const ld PI = 3.1415926535897932384626433832795;
  43.  
  44. const int NMAX = 2000;
  45.  
  46. int a[NMAX][NMAX], r[NMAX], c[NMAX], mr[NMAX], mc[NMAX];
  47. int n, m;
  48.  
  49. int main() {
  50.     #ifdef myproject
  51.     freopen("input.txt", "rt", stdin);
  52.     //freopen("output.txt", "wt", stdout);
  53.     #endif
  54.  
  55.     srand(time(NULL));
  56.  
  57.     scanf("%d%d", &n, &m);
  58. //    n = rand()%100+1;
  59. //    m = rand()%100+1;
  60.  
  61.     forn(i, n)
  62.         forn(j, m){
  63.             scanf("%d", &a[i][j]);
  64. //            a[i][j] = rand()%100 - 50;
  65.         }
  66.  
  67.     forn(i, n){
  68.         forn(j, m){
  69.             r[i] += a[i][j];
  70.             c[j] += a[i][j];
  71.         }            
  72.     }
  73.  
  74.     forn(i, n)
  75.         mr[i] = 1;
  76.     forn(j, m)
  77.         mc[j] = 1;
  78.  
  79.     #ifdef myproject
  80.     cout << n << " " << m << endl;
  81.     forn(i, n){
  82.         forn(j, m){
  83.             cout << a[i][j]*mr[i]*mc[j] << " ";            
  84.         }
  85.         cout << endl;
  86.     }
  87.     #endif
  88.  
  89.  
  90.     int iter = 0;
  91.    
  92.     while(true){
  93.        
  94.         iter++;
  95.  
  96.         int rid = -1;
  97.         forn(i, n){
  98.             if(r[i] < 0){
  99.                 rid = i;
  100.                 break;
  101.             }
  102.         }
  103.        
  104.         if(rid != -1){
  105.             forn(j, m){
  106.                 c[j] -= a[rid][j] * mr[rid] * mc[j];
  107.             }
  108.             mr[rid] *= -1;
  109.             forn(j, m){
  110.                 c[j] += a[rid][j] * mr[rid] * mc[j];
  111.             }
  112.  
  113.             r[rid] *= -1;
  114.             continue;
  115.         }
  116.  
  117.  
  118.         int cid = -1;
  119.         forn(j, m){
  120.             if(c[j] < 0){
  121.                 cid = j;
  122.                 break;
  123.             }
  124.         }
  125.  
  126.         if(cid != -1){
  127.             forn(i, n){
  128.                 r[i] -= a[i][cid] * mc[cid] * mr[i];
  129.             }
  130.             mc[cid] *= -1;
  131.             forn(i, n){
  132.                 r[i] += a[i][cid] * mc[cid] * mr[i];
  133.             }
  134.             c[cid] *= -1;
  135.             continue;
  136.         }
  137.  
  138.         break;
  139.     }
  140.  
  141.     vector<int> nr(n), nc(m);
  142.     forn(i, n){
  143.         forn(j, m){
  144.             nr[i] += a[i][j] * mr[i] * mc[j];            
  145.             nc[j] += a[i][j] * mr[i] * mc[j];
  146.         }
  147.     }
  148.  
  149.     assert(*min_element(all(nr)) >= 0);
  150.     assert(*max_element(all(nc)) >= 0);
  151.  
  152.     /*
  153.     cout << endl;
  154.     forn(i, n){
  155.         forn(j, m){
  156.             cout << a[i][j]*mr[i]*mc[j] << " ";            
  157.         }
  158.         cout << endl;
  159.     }*/
  160.  
  161.     vector<int> rr, cc;
  162.     forn(i, n)
  163.         if(mr[i] == -1)
  164.             rr.pb(i);
  165.     forn(j, m)
  166.         if(mc[j] == -1)
  167.             cc.pb(j);
  168.    
  169.     cout << sz(rr) << " ";
  170.     forn(i, sz(rr))
  171.         cout << rr[i]+1 << " ";
  172.     cout << endl;
  173.     cout << sz(cc) << " ";
  174.     forn(i, sz(cc))
  175.         cout << cc[i]+1 << " ";
  176.     cout << endl;
  177.  
  178.  
  179.     #ifdef myproject
  180.     cerr << "Iterations = " << iter << endl;
  181.     #endif
  182.  
  183.     return 0;
  184. }
RAW Paste Data