Submission #1174255


Source Code Expand

#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=(b-1);i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;
 
#define MOD 1000000007
 
unsigned int xor128(void) {
  static unsigned int x = 123456789;
  static unsigned int y = 362436069;
  static unsigned int z = 521288629;
  static unsigned int w = 88675123;
  unsigned int t;
 
  t = x ^ (x << 11);
  x = y; y = z; z = w;
  return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
 
ll H, W, K, T;
vector<pair<pair<pair<ll, ll>, pair<ll, ll> >, ll> > v;
map<ll, pair<ll, ll> > ma;
map<pair<ll, ll>, ll> mi;
 
ll g(ll y1, ll x1) {
  ll ret = 0;
  rep(y2, y1, y1 + 2) {
    rep(x2, x1, x1 + 2) {
      if (mi[mp(y2, x2)] != 0) {
        ll index = mi[mp(y2, x2)];
        ll gy = v[index - 1].fi.se.fi;
        ll gx = v[index - 1].fi.se.se;
        ret += abs(y2 - gy) + abs(x2 - gx);
      }
    }
  }
  return ret;
}
 
ll dd[10100];
 
int main() {
  vector<string> ans;
  cin >> H >> W >> K >> T;
  rep(i, 0, K) {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    a--; b--; c--; d--;
    v.pb(mp(mp(mp(a, b), mp(c, d)), i));
    ma[i + 1] = mp(a, b);
    mi[mp(a, b)] = i + 1;
  }
  rep(q, 0, T) {
    ll dy = q & 1;
    ll dx = (q >> 1) & 1;
    string s;
    rep(i, 0, K)s += "-";
    for (int y1 = dy; y1 < H - 1; y1 += 2) {
      for (int x1 = dx; x1 < W - 1; x1 += 2) {
        ll temp0[4];
        temp0[0] = mi[mp(y1, x1)];
        temp0[1] = mi[mp(y1, x1 + 1)];
        temp0[2] = mi[mp(y1 + 1, x1 + 1)];
        temp0[3] = mi[mp(y1 + 1, x1)];
 
        // cw
        ll index_cw = -1;
        ll mx_cw = g(y1, x1);
        rep(i, 0, 1 << 4) {
          mi[mp(y1, x1)] = temp0[0];
          mi[mp(y1, x1 + 1)] = temp0[1];
          mi[mp(y1 + 1, x1 + 1)] = temp0[2];
          mi[mp(y1 + 1, x1)] = temp0[3];
          if (((i >> 0) & 1) == 1) {
            if (temp0[0] != 0 && temp0[1] == 0) {
              swap(mi[mp(y1, x1)], mi[mp(y1, x1 + 1)]);
            }
          }
          if (((i >> 1) & 1) == 1) {
            if (temp0[1] != 0 && temp0[2] == 0) {
              swap(mi[mp(y1, x1 + 1)], mi[mp(y1 + 1, x1 + 1)]);
            }
          }
          if (((i >> 2) & 1) == 1) {
            if (temp0[2] != 0 && temp0[3] == 0) {
              swap(mi[mp(y1 + 1, x1 + 1)], mi[mp(y1 + 1, x1)]);
            }
          }
          if (((i >> 3) & 1) == 1) {
            if (temp0[3] != 0 && temp0[0] == 0) {
              swap(mi[mp(y1 + 1, x1)], mi[mp(y1, x1)]);
            }
          }
          ll score = g(y1, x1);
          if (score <= mx_cw) {
            index_cw = i;
          }
        }
 
        mi[mp(y1, x1)] = temp0[0];
        mi[mp(y1, x1 + 1)] = temp0[1];
        mi[mp(y1 + 1, x1 + 1)] = temp0[2];
        mi[mp(y1 + 1, x1)] = temp0[3];
 
        // ccw
        ll index_ccw = -1;
        ll mx_ccw = g(y1, x1);
        rep(i, 0, 1 << 4) {
          mi[mp(y1, x1)] = temp0[0];
          mi[mp(y1, x1 + 1)] = temp0[1];
          mi[mp(y1 + 1, x1 + 1)] = temp0[2];
          mi[mp(y1 + 1, x1)] = temp0[3];
          if (((i >> 0) & 1) == 1) {
            if (temp0[0] != 0 && temp0[3] == 0) {
              swap(mi[mp(y1, x1)], mi[mp(y1 + 1, x1 + 1)]);
            }
          }
          if (((i >> 1) & 1) == 1) {
            if (temp0[1] != 0 && temp0[0] == 0) {
              swap(mi[mp(y1, x1 + 1)], mi[mp(y1, x1)]);
            }
          }
          if (((i >> 2) & 1) == 1) {
            if (temp0[2] != 0 && temp0[1] == 0) {
              swap(mi[mp(y1 + 1, x1 + 1)], mi[mp(y1, x1 + 1)]);
            }
          }
          if (((i >> 3) & 1) == 1) {
            if (temp0[3] != 0 && temp0[2] == 0) {
              swap(mi[mp(y1 + 1, x1)], mi[mp(y1 + 1, x1 + 1)]);
            }
          }
          ll score = g(y1, x1);
          if (score <= mx_ccw) {
            index_ccw = i;
          }
        }
 
        mi[mp(y1, x1)] = temp0[0];
        mi[mp(y1, x1 + 1)] = temp0[1];
        mi[mp(y1 + 1, x1 + 1)] = temp0[2];
        mi[mp(y1 + 1, x1)] = temp0[3];
 
        if(q%5==0){
          index_cw = xor128()%(1<<4);
          index_ccw = xor128()%(1<<4);
        }

        if (mx_cw >= mx_ccw) {
          rep(i, 0, 1 << 4) {
            if (i == index_cw) {
              if (((i >> 0) & 1) == 1) {
                if (temp0[0] != 0 && temp0[1] == 0) {
                  s[temp0[0] - 1] = 'R';
                  swap(mi[mp(y1, x1)], mi[mp(y1, x1 + 1)]);
                }
              }
              if (((i >> 1) & 1) == 1) {
                if (temp0[1] != 0 && temp0[2] == 0) {
                  s[temp0[1] - 1] = 'D';
                  swap(mi[mp(y1, x1 + 1)], mi[mp(y1 + 1, x1 + 1)]);
                }
              }
              if (((i >> 2) & 1) == 1) {
                if (temp0[2] != 0 && temp0[3] == 0) {
                  s[temp0[2] - 1] = 'L';
                  swap(mi[mp(y1 + 1, x1 + 1)], mi[mp(y1 + 1, x1)]);
                }
              }
              if (((i >> 3) & 1) == 1) {
                if (temp0[3] != 0 && temp0[0] == 0) {
                  s[temp0[3] - 1] = 'U';
                  swap(mi[mp(y1 + 1, x1)], mi[mp(y1, x1)]);
                }
              }
            }
          }
        }
        else {
          rep(i, 0, 1 << 4) {
            if (i == index_ccw) {
              if (((i >> 0) & 1) == 1) {
                if (temp0[0] != 0 && temp0[3] == 0) {
                  s[temp0[0] - 1] = 'D';
                  swap(mi[mp(y1, x1)], mi[mp(y1 + 1, x1 + 1)]);
                }
              }
              if (((i >> 1) & 1) == 1) {
                if (temp0[1] != 0 && temp0[0] == 0) {
                  s[temp0[1] - 1] = 'L';
                  swap(mi[mp(y1, x1 + 1)], mi[mp(y1, x1)]);
                }
              }
              if (((i >> 2) & 1) == 1) {
                if (temp0[2] != 0 && temp0[1] == 0) {
                  s[temp0[2] - 1] = 'U';
                  swap(mi[mp(y1 + 1, x1 + 1)], mi[mp(y1, x1 + 1)]);
                }
              }
              if (((i >> 3) & 1) == 1) {
                if (temp0[3] != 0 && temp0[2] == 0) {
                  s[temp0[3] - 1] = 'R';
                  swap(mi[mp(y1 + 1, x1)], mi[mp(y1 + 1, x1 + 1)]);
                }
              }
            }
          }
        }
      }
    }
    ans.pb(s);
    if(ans.sz==1000){
      break;
    }
  }
  cout << ans.sz << endl;
  rep(i,0,ans.sz){
    cout << ans[i] << endl;
  }
  return 0;
}

Submission Info

Submission Time
Task B - 日本橋大渋滞
User nmnmnmnmnmnmnm
Language C++14 (GCC 5.4.1)
Score 3186
Code Size 7232 Byte
Status AC
Exec Time 2149 ms
Memory 1280 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10 test_11 test_12 test_13 test_14 test_15 test_16 test_17 test_18 test_19 test_20 test_21 test_22 test_23 test_24 test_25 test_26 test_27 test_28 test_29 test_30
Score / Max Score 128 / 50000 123 / 50000 112 / 50000 115 / 50000 115 / 50000 103 / 50000 99 / 50000 114 / 50000 100 / 50000 104 / 50000 109 / 50000 109 / 50000 98 / 50000 118 / 50000 99 / 50000 107 / 50000 97 / 50000 107 / 50000 97 / 50000 103 / 50000 112 / 50000 113 / 50000 106 / 50000 95 / 50000 107 / 50000 101 / 50000 109 / 50000 87 / 50000 99 / 50000 100 / 50000
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
test_11 subtask_01_11.txt
test_12 subtask_01_12.txt
test_13 subtask_01_13.txt
test_14 subtask_01_14.txt
test_15 subtask_01_15.txt
test_16 subtask_01_16.txt
test_17 subtask_01_17.txt
test_18 subtask_01_18.txt
test_19 subtask_01_19.txt
test_20 subtask_01_20.txt
test_21 subtask_01_21.txt
test_22 subtask_01_22.txt
test_23 subtask_01_23.txt
test_24 subtask_01_24.txt
test_25 subtask_01_25.txt
test_26 subtask_01_26.txt
test_27 subtask_01_27.txt
test_28 subtask_01_28.txt
test_29 subtask_01_29.txt
test_30 subtask_01_30.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 2093 ms 1280 KB
subtask_01_02.txt AC 2117 ms 1280 KB
subtask_01_03.txt AC 2098 ms 1280 KB
subtask_01_04.txt AC 2094 ms 1280 KB
subtask_01_05.txt AC 2092 ms 1280 KB
subtask_01_06.txt AC 2076 ms 1280 KB
subtask_01_07.txt AC 2101 ms 1280 KB
subtask_01_08.txt AC 2088 ms 1280 KB
subtask_01_09.txt AC 2100 ms 1280 KB
subtask_01_10.txt AC 2100 ms 1280 KB
subtask_01_11.txt AC 2107 ms 1280 KB
subtask_01_12.txt AC 2104 ms 1280 KB
subtask_01_13.txt AC 2059 ms 1280 KB
subtask_01_14.txt AC 2135 ms 1280 KB
subtask_01_15.txt AC 2076 ms 1280 KB
subtask_01_16.txt AC 2085 ms 1280 KB
subtask_01_17.txt AC 2059 ms 1280 KB
subtask_01_18.txt AC 2056 ms 1280 KB
subtask_01_19.txt AC 2081 ms 1280 KB
subtask_01_20.txt AC 2083 ms 1280 KB
subtask_01_21.txt AC 2085 ms 1280 KB
subtask_01_22.txt AC 2149 ms 1280 KB
subtask_01_23.txt AC 2104 ms 1280 KB
subtask_01_24.txt AC 2062 ms 1280 KB
subtask_01_25.txt AC 2100 ms 1280 KB
subtask_01_26.txt AC 2090 ms 1280 KB
subtask_01_27.txt AC 2093 ms 1280 KB
subtask_01_28.txt AC 2044 ms 1280 KB
subtask_01_29.txt AC 2092 ms 1280 KB
subtask_01_30.txt AC 2105 ms 1280 KB