SHARE
TWEET

Unity Deadline24 by Psyho

a guest Mar 21st, 2014 298 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <unistd.h>
  3. #include <glpk.h>
  4.  
  5. #ifdef __CYGWIN__
  6. #define cimg_OS 2
  7. #define _fileno fileno
  8. #define _getpid getpid
  9. #define _vsnprintf vsnprintf
  10. #define _snprintf snprintf
  11. #endif
  12. #include <CImg.h>
  13.  
  14. using namespace cimg_library;
  15. using namespace std;
  16.  
  17. #define FORE(it,c)  for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
  18. #define FOR(i,a,b)  for(int i=(a);i<(b);++i)
  19. #define REP(i,a)    FOR(i,0,a)
  20. #define ZERO(m)    memset(m,0,sizeof(m))
  21. #define ALL(x)      x.begin(),x.end()
  22. #define PB          push_back
  23. #define S          size()
  24. #define LL          long long
  25. #define ULL        unsigned long long
  26. #define LD          long double
  27. #define MP          make_pair
  28. #define X          first
  29. #define Y          second
  30. #define VC          vector
  31. #define PII        pair <int, int>
  32. #define VI          VC < int >
  33. #define VVI        VC < VI >
  34. #define VD          VC < double >
  35. #define VVD        VC < VD >
  36. #define VS          VC < string >
  37. #define DB(a)      cerr << #a << ": " << (a) << endl;
  38.  
  39. template<class T> void print(VC < T > v) {cerr << "[";if (v.S) cerr << v[0];FOR(i, 1, v.S) cerr << ", " << v[i];cerr << "]\n";}
  40. template<class T> string i2s(T x) {ostringstream o; o << x; return o.str(); }
  41. VS splt(string s, char c = ' ') {VS all; int p = 0, np; while (np = s.find(c, p), np >= 0) {if (np != p) all.PB(s.substr(p, np - p)); p = np + 1;} if (p < s.S) all.PB(s.substr(p)); return all;}
  42.  
  43. int R, C;
  44. int shapes;
  45. int data[64][64];
  46. int shape[64][64];
  47. int tmp[64][64];
  48. int res[64][64];
  49.  
  50. glp_prob *lp;
  51.  
  52. bool ok(int r, int c) {
  53.         return r >= 0 && r < R && c >= 0 && c < C && data[r][c];
  54. }
  55.  
  56. VS solve() {
  57.         VI lpr, lpc;
  58.         VD lpv;
  59.         VS pos;
  60.        
  61.         lpr.PB(0);
  62.         lpc.PB(0);
  63.         lpv.PB(0);
  64.        
  65.         int rows = 0;
  66.         REP(r, R) REP(c, C) rows += data[r][c];
  67.        
  68.         REP(rot, 4) {
  69.                 memcpy(tmp, shape, sizeof(shape));
  70.                 REP(i, 64) REP(j, 64)
  71.                         shape[j][63-i] = tmp[i][j];
  72.                        
  73.                 FOR(offr, -64, 64) FOR(offc, -64, 64) {
  74.                         string s = "";
  75.                         REP(r, 64) REP(c, 64) if (shape[r][c] && !ok(r + offr, c + offc)) goto next;
  76.                        
  77.                         ZERO(tmp);
  78.                         REP(r, 64) REP(c, 64) if (shape[r][c]) {
  79.                                 tmp[r + offr][c + offc] = 1;
  80.                                 lpr.PB((r + offr) * 64 + (c + offc) + 1);
  81.                                 lpc.PB(pos.S + 1);
  82.                                 lpv.PB(1.0);
  83.                         }
  84.                         REP(r, 64) REP(c, 64) s += tmp[r][c] ? '1' : '0';
  85.                         pos.PB(s);
  86.                         next: ;
  87.                 }
  88.                
  89.         }
  90.        
  91.         glp_term_out(GLP_OFF);
  92.         lp = glp_create_prob();
  93.        
  94.         glp_set_prob_name(lp, "sample");
  95.         glp_set_obj_dir(lp, GLP_MAX);
  96.        
  97.         glp_add_rows(lp, 64 * 64);
  98.         REP(r, 64) REP(c, 64) glp_set_row_bnds(lp, r * 64 + c + 1, GLP_DB, 0.0, 1.0);
  99.        
  100.         glp_add_cols(lp, pos.S);
  101.         REP(i, pos.S) {
  102.                 glp_set_col_bnds(lp, i + 1, GLP_DB, 0.0, 1.0);
  103.                 glp_set_obj_coef(lp, i + 1, 1.0);
  104.                 glp_set_col_kind(lp, i + 1, GLP_BV);
  105.         }      
  106.        
  107.         glp_load_matrix(lp, lpr.S - 1, &lpr[0], &lpc[0], &lpv[0]);
  108.        
  109.         glp_iocp parm;
  110.         glp_init_iocp(&parm);
  111.         parm.presolve = GLP_ON;
  112.         parm.cb_func = NULL;
  113.         parm.cb_info = NULL;
  114.         glp_intopt(lp, &parm);
  115.        
  116.         int no = glp_mip_obj_val(lp);
  117.         cout << "Shapes Found: " << no << endl;
  118.        
  119.         VS rv;
  120.         REP(i, pos.S) if (glp_mip_col_val(lp, i + 1)) rv.PB(pos[i]);
  121.        
  122.         glp_delete_prob(lp);
  123.        
  124.         return rv;
  125. }
  126.  
  127. void calcres(VS v) {
  128.         ZERO(res);
  129.         REP(i, v.S) REP(r, 64) REP(c, 64) if (v[i][r * 64 + c] == '1') res[r][c] = 1 + i;
  130. }
  131.  
  132. void output() {
  133.         REP(r, R) {
  134.                 REP(c, C) {
  135.                         char cc = ' ';
  136.                         if (data[r][c]) cc = '#';
  137.                         if (res[r][c] >= 1 && res[r][c] <= 26) cc = 'A' + res[r][c] - 1;
  138.                         if (res[r][c] >= 27) cc = 'a' + res[r][c] - 27;
  139.                         cout << cc;
  140.                 }
  141.                 cout << endl;
  142.         }
  143. }
  144.  
  145. CImg < unsigned char > img;
  146. CImgDisplay disp;
  147.  
  148. const int CELL_SIZE = 20;
  149. const int MARGIN = 2;
  150.  
  151. unsigned char white[] = {255, 255, 255};
  152. unsigned char grey[] = {192, 192, 192};
  153. unsigned char red[] = {255, 128, 64};
  154. unsigned char green[] = {128, 255, 128};
  155. void draw() {
  156.         img = (unsigned char)0;
  157.        
  158.         bool selectingShape = true;
  159.         REP(r, 64) REP(c, 64) selectingShape &= res[r][c] == 0;
  160.        
  161.         REP(r, R) REP(c, C)
  162.                 if (data[r][c]) img.draw_rectangle(c * CELL_SIZE + MARGIN, r * CELL_SIZE + MARGIN, (c + 1) * CELL_SIZE - MARGIN, (r + 1) * CELL_SIZE - MARGIN, res[r][c] ? white : selectingShape && shape[r][c] ? green : grey);
  163.  
  164.         REP(r, R) REP(c, C) if (res[r][c]) {
  165.                 if (r == 0 || res[r-1][c] != res[r][c]) img.draw_rectangle(c * CELL_SIZE - 1, r * CELL_SIZE - 1, (c + 1) * CELL_SIZE + 1, r * CELL_SIZE + 1, red);
  166.                 if (r == R - 1 || res[r+1][c] != res[r][c]) img.draw_rectangle(c * CELL_SIZE - 1, (r + 1) * CELL_SIZE - 1, (c + 1) * CELL_SIZE + 1, (r + 1) * CELL_SIZE + 1, red);
  167.                 if (c == 0 || res[r][c-1] != res[r][c]) img.draw_rectangle(c * CELL_SIZE - 1, r * CELL_SIZE - 1, c * CELL_SIZE + 1, (r + 1) * CELL_SIZE + 1, red);
  168.                 if (c == C - 1 || res[r][c+1] != res[r][c]) img.draw_rectangle((c + 1) * CELL_SIZE - 1, r * CELL_SIZE - 1, (c + 1) * CELL_SIZE + 1, (r + 1) * CELL_SIZE + 1, red);
  169.         }
  170. }
  171.  
  172.  
  173. int main(int argc, char **argv) {
  174.         assert(argc > 1);
  175.  
  176.         int fileNo = atoi(argv[1]);
  177.         int testNo = argc > 2 ? atoi(argv[2]) : 0;
  178.        
  179.         string fn = "unity" + i2s(fileNo / 10) + i2s(fileNo % 10) + ".in";
  180.         ifstream fs(fn.c_str());
  181.        
  182.         int tc;
  183.         fs >> tc;
  184.        
  185.         while (true) {
  186.                 fs >> shapes >> R >> C;
  187.                 REP(i, R) {
  188.                         string s;
  189.                         fs >> s;
  190.                         REP(j, C) data[i][j] = s[j] == '#';
  191.                 }
  192.                 if (testNo-- == 0) break;
  193.         }
  194.         fs.close();
  195.        
  196.         img = CImg<unsigned char>(C * CELL_SIZE, R * CELL_SIZE, 1, 3);
  197.        
  198.         int x = 0;
  199.         REP(r, R) REP(c, C) x += data[r][c];
  200.         cout << "Number of Shapes: " << shapes << endl;
  201.         cout << "Size of Shapes: " << (x / shapes) << endl;
  202.        
  203.         ZERO(shape);
  204.        
  205.         int mouseButtons = 0;
  206.         int lastR = 0, lastC = 0;
  207.         while (true) {
  208.                 draw();
  209.                 disp.display(img);
  210.                
  211.                 disp.wait();
  212.                 if (disp.is_keyQ()) break;
  213.                 if (disp.is_keyN()) ZERO(res);
  214.                 if (disp.is_keyC()) ZERO(res), ZERO(shape);
  215.                 if (disp.is_keyR()) {
  216.                         VS rv = solve();
  217.                         calcres(rv);
  218.                         output();
  219.                 }
  220.                 int r = disp.mouse_y() / CELL_SIZE;
  221.                 int c = disp.mouse_x() / CELL_SIZE;
  222.                 if ((disp.button() & 1) && ((mouseButtons & 1) == 0 || lastR != r || lastC != c)) {
  223.                         if (data[r][c]) shape[r][c] = 1 - shape[r][c];
  224.                 }
  225.                 mouseButtons = disp.button();
  226.                 lastR = r;
  227.                 lastC = c;
  228.         }
  229.        
  230.         return 0;      
  231. }
RAW Paste Data
Want to get better at C++?
Learn to code C++ in 2017
Top