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 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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 |