QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#590494 | #9304. Sean the Cuber | sparkuggz | AC ✓ | 10287ms | 176092kb | C++14 | 7.2kb | 2024-09-26 01:02:12 | 2024-09-26 01:02:12 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <ctime>
#include <unordered_map>
#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define Rep(i, n) for (int i = 1; i <= (n); ++i)
#define clr(x, a) memset(x, (a), sizeof x)
using namespace std;
typedef long long ll;
int const u1[4] = { 6,7,15,14 };
int const u2[8] = { 2,3,8,16,21,20,13,5 };
int const d1[4] = { 11,10,18,19 };
int const d2[8] = { 0,1,9,17,23,22,12,4 };
int const r1[4] = { 8,9,17,16 };
int const r2[8] = { 23,21,15,7,3,1,10,18 };
int const l1[4] = { 5,4,12,13 };
int const l2[8] = { 22,20,14,6,2,0,11,19 };
int const f1[4] = { 20,21,23,22 };
int const f2[8] = { 12,13,14,15,16,17,18,19 };
int const b1[4] = { 2,3,1,0 };
int const b2[8] = { 4,5,6,7,8,9,10,11 };
int ss[30], ts[30];
ll U(ll s) {
rep(i, 24) {
ts[23 - i] = ss[23 - i] = s % 6;
s /= 6;
}
rep(i, 4) ts[u1[i]] = ss[u1[(i + 3) & 3]];
rep(i, 8) ts[u2[i]] = ss[u2[(i + 6) & 7]];
ll r = 0; rep(i, 24) r = r * 6 + ts[i];
return r;
}
ll UT(ll s) {
rep(i, 24) {
ts[23 - i] = ss[23 - i] = s % 6;
s /= 6;
}
rep(i, 4) ts[u1[i]] = ss[u1[(i + 1) & 3]];
rep(i, 8) ts[u2[i]] = ss[u2[(i + 2) & 7]];
ll r = 0; rep(i, 24) r = r * 6 + ts[i];
return r;
}
ll R(ll s) {
rep(i, 24) {
ts[23 - i] = ss[23 - i] = s % 6;
s /= 6;
}
rep(i, 4) ts[r1[i]] = ss[r1[(i + 3) & 3]];
rep(i, 8) ts[r2[i]] = ss[r2[(i + 6) & 7]];
ll r = 0; rep(i, 24) r = r * 6 + ts[i];
return r;
}
ll RT(ll s) {
rep(i, 24) {
ts[23 - i] = ss[23 - i] = s % 6;
s /= 6;
}
rep(i, 4) ts[r1[i]] = ss[r1[(i + 1) & 3]];
rep(i, 8) ts[r2[i]] = ss[r2[(i + 2) & 7]];
ll r = 0; rep(i, 24) r = r * 6 + ts[i];
return r;
}
ll F(ll s) {
rep(i, 24) {
ts[23 - i] = ss[23 - i] = s % 6;
s /= 6;
}
rep(i, 4) ts[f1[i]] = ss[f1[(i + 3) & 3]];
rep(i, 8) ts[f2[i]] = ss[f2[(i + 6) & 7]];
ll r = 0; rep(i, 24) r = r * 6 + ts[i];
return r;
}
ll FT(ll s) {
rep(i, 24) {
ts[23 - i] = ss[23 - i] = s % 6;
s /= 6;
}
rep(i, 4) ts[f1[i]] = ss[f1[(i + 1) & 3]];
rep(i, 8) ts[f2[i]] = ss[f2[(i + 2) & 7]];
ll r = 0; rep(i, 24) r = r * 6 + ts[i];
return r;
}
ll UD(ll s) {
rep(i, 24) {
ts[23 - i] = ss[23 - i] = s % 6;
s /= 6;
}
rep(i, 4) ts[u1[i]] = ss[u1[(i + 1) & 3]];
rep(i, 8) ts[u2[i]] = ss[u2[(i + 2) & 7]];
rep(i, 8) ts[d2[i]] = ss[d2[(i + 2) & 7]];
rep(i, 4) ts[d1[i]] = ss[d1[(i + 1) & 3]];
ll r = 0; rep(i, 24) r = r * 6 + ts[i];
return r;
}
ll RL(ll s) {
rep(i, 24) {
ts[23 - i] = ss[23 - i] = s % 6;
s /= 6;
}
rep(i, 4) ts[r1[i]] = ss[r1[(i + 1) & 3]];
rep(i, 8) ts[r2[i]] = ss[r2[(i + 2) & 7]];
rep(i, 8) ts[l2[i]] = ss[l2[(i + 2) & 7]];
rep(i, 4) ts[l1[i]] = ss[l1[(i + 1) & 3]];
ll r = 0; rep(i, 24) r = r * 6 + ts[i];
return r;
}
ll FB(ll s) {
rep(i, 24) {
ts[23 - i] = ss[23 - i] = s % 6;
s /= 6;
}
rep(i, 4) ts[f1[i]] = ss[f1[(i + 1) & 3]];
rep(i, 8) ts[f2[i]] = ss[f2[(i + 2) & 7]];
rep(i, 8) ts[b2[i]] = ss[b2[(i + 2) & 7]];
rep(i, 4) ts[b1[i]] = ss[b1[(i + 1) & 3]];
ll r = 0; rep(i, 24) r = r * 6 + ts[i];
return r;
}
unordered_map<ll, int> f;
queue<ll> q;
void upd(ll z, int val) {
if (!f.count(z)) {
f[z] = val;
q.push(z);
}
}
void init(string s0 = "000011223344112233445555") {
ll z0 = 0;
rep(i, 24) z0 = z0 * 6 + (s0[i] - '0');
f.clear();
f[z0] = 0; q.push(z0);
while (!q.empty()) {
ll t = q.front(); q.pop();
int val = f[t] + 1;
upd(U(t), val);
upd(UT(t), val);
upd(R(t), val);
upd(RT(t), val);
upd(F(t), val);
upd(FT(t), val);
}
}
int lf[24], up[24];
int const col[24] = { 0,0,0,0,1,1,2,2,3,3,4,4,1,1,2,2,3,3,4,4,5,5,5,5 };
int mp2[6][6][3], mp4[6][6][3];
int cmp[128];
void initmp() {
lf[0] = 4; up[0] = 11; lf[1] = 10; up[1] = 9; lf[2] = 6; up[2] = 5; lf[3] = 8; up[3] = 7;
lf[4] = 11; up[4] = 0; lf[5] = 2; up[5] = 6; lf[6] = 5; up[6] = 2; lf[7] = 3; up[7] = 8;
lf[8] = 7; up[8] = 3; lf[9] = 1; up[9] = 10; lf[10] = 9; up[10] = 1; lf[11] = 0; up[11] = 4;
lf[12] = 22; up[12] = 19; lf[13] = 14; up[13] = 20; lf[14] = 20; up[14] = 13; lf[15] = 16; up[15] = 21;
lf[16] = 21; up[16] = 15; lf[17] = 18; up[17] = 23; lf[18] = 23; up[18] = 17; lf[19] = 12; up[19] = 22;
lf[20] = 13; up[20] = 14; lf[21] = 15; up[21] = 16; lf[22] = 19; up[22] = 12; lf[23] = 17; up[23] = 18;
rep(i, 24) if (col[i] == 2) {
mp2[ col[ lf[i] ] ][ col [ up[i] ] ][0] = i;
mp2[ col[ lf[i] ] ][ col [ up[i] ] ][1] = lf[i];
mp2[ col[ lf[i] ] ][ col [ up[i] ] ][2] = up[i];
}
rep(i, 24) if (col[i] == 4) {
mp4[ col[ lf[i] ] ][ col [ up[i] ] ][0] = i;
mp4[ col[ lf[i] ] ][ col [ up[i] ] ][1] = lf[i];
mp4[ col[ lf[i] ] ][ col [ up[i] ] ][2] = up[i];
}
cmp['Y'] = 0; cmp['O'] = 1; cmp['B'] = 2; cmp['R'] = 3; cmp['G'] = 4; cmp['W'] = 5;
}
int ra[24], rb[24];
char buf[111];
int rc[24];
int main() {
init();
initmp();
int T; scanf("%d", &T);
while (T--) {
ll sa = 0, sb = 0;
rep(k, 14) {
scanf(" %s", buf);
int z = strlen(buf);
bool split = 0;
if (k == 2 || k == 5 || k == 10 || k == 13) split = 1;
rep(i, z) {
if (buf[i] == '|') { split = 1; continue; }
else if (buf[i] == ' ') continue;
if (!split) sa = sa * 6 + cmp[buf[i]];
else sb = sb * 6 + cmp[buf[i]];
}
}
rep(i, 4) {
sa = UD(sa);
rep(j, 4) {
sa = RL(sa);
rep(k, 4) {
sa = FB(sa);
if (f.count(sa)) {
goto suc1;
}
}
}
}
suc1:;
rep(i, 4) {
sb = UD(sb);
rep(j, 4) {
sb = RL(sb);
rep(k, 4) {
sb = FB(sb);
if (f.count(sb)) {
goto suc2;
}
}
}
}
suc2:;
rep(i, 24) {
ra[23 - i] = sa % 6; sa /= 6;
rb[23 - i] = sb % 6; sb /= 6;
}
int rk[24]; rep(i, 24) rk[i] = ra[i];
rep(i, 24) {
if (rk[i] == 2) {
int x = mp2[rk[lf[i]]][rk[up[i]]][0], y = mp2[rk[lf[i]]][rk[up[i]]][1], z = mp2[rk[lf[i]]][rk[up[i]]][2];
ra[i] = x; ra[lf[i]] = y; ra[up[i]] = z;
} else if (rk[i] == 4) {
int x = mp4[rk[lf[i]]][rk[up[i]]][0], y = mp4[rk[lf[i]]][rk[up[i]]][1], z = mp4[rk[lf[i]]][rk[up[i]]][2];
ra[i] = x; ra[lf[i]] = y; ra[up[i]] = z;
}
}
rep(i, 24) rk[i] = rb[i];
rep(i, 24) {
if (rk[i] == 2) {
int x = mp2[rk[lf[i]]][rk[up[i]]][0], y = mp2[rk[lf[i]]][rk[up[i]]][1], z = mp2[rk[lf[i]]][rk[up[i]]][2];
rb[i] = x; rb[lf[i]] = y; rb[up[i]] = z;
} else if (rk[i] == 4) {
int x = mp4[rk[lf[i]]][rk[up[i]]][0], y = mp4[rk[lf[i]]][rk[up[i]]][1], z = mp4[rk[lf[i]]][rk[up[i]]][2];
rb[i] = x; rb[lf[i]] = y; rb[up[i]] = z;
}
}
rep(i, 24) rk[ra[i]] = i;
rep(i, 24) {
rc[i] = col[rk[rb[i]]];
}
ll s = 0; rep(i, 24) s = s * 6 + rc[i];
printf("%d\n", f[s]);
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7775ms
memory: 176092kb
input:
2 GO | WG GO | WY OOYBYWBW|ROGBRYRG RRYRBWRB|BOGBWYBW GY | YO WG | RO WR | YR OR | OW OYGBWGYB|OWBRBYBG BWGWRBYY|YOWRYGWO OG | GG OR | BR
output:
2 11
result:
ok 2 number(s): "2 11"
Test #2:
score: 0
Accepted
time: 10287ms
memory: 175936kb
input:
250000 BG | WB GG | RG YOYYRWOR|OYBRWWRB YRWWRWOO|OOGOWRYB BG | YG BB | YG OB | RO RG | GB WBWRWRYG|WRWRYGWB RYOBOWOG|OBOWOGRY GY | YB YB | GY GR | YR OB | OO WWBYOYBR|RBYYGBWB Y...
output:
2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 250000 numbers
Test #3:
score: 0
Accepted
time: 7794ms
memory: 175792kb
input:
100 BG | WB GG | RG YOYYRWOR|OYBRWWRB YRWWRWOO|OOGOWRYB BG | YG BB | YG GB | BY OG | GG RBYWOWRY|RYROYOBW ORGBWBYY|ORBWROWW WO | YG GR | BG YB | YW BO | WW RWRYGOWB|BBORBGRO WGOB...
output:
2 10 7 10 10 9 11 10 12 11 9 10 10 12 10 11 11 10 12 12 10 11 10 11 12 10 10 10 11 9 12 9 10 10 10 11 12 12 11 11 10 11 9 11 8 11 11 12 13 10 10 12 11 10 11 11 11 10 12 10 11 12 11 11 11 11 10 10 10 11 12 12 11 11 11 11 11 12 10 12 11 8 11 12 10 11 11 11 12 11 10 11 12 10 9 9 9 11 11 11
result:
ok 100 numbers
Test #4:
score: 0
Accepted
time: 7774ms
memory: 176072kb
input:
1000 BG | WB GG | RG YOYYRWOR|OYBRWWRB YRWWRWOO|OOGOWRYB BG | YG BB | YG GB | BY OG | GG RBYWOWRY|RYROYOBW ORGBWBYY|ORBWROWW WO | YG GR | BG YB | YW BO | WW RWRYGOWB|BBORBGRO WGO...
output:
2 10 7 10 10 9 11 10 12 11 9 10 10 12 10 11 11 10 12 12 10 11 10 11 12 10 10 10 11 9 12 9 10 10 10 11 12 12 11 11 10 11 9 11 8 11 11 12 13 10 10 12 11 10 11 11 11 10 12 10 11 12 11 11 11 11 10 10 10 11 12 12 11 11 11 11 11 12 10 12 11 8 11 12 10 11 11 11 12 11 10 11 12 10 9 9 9 11 11 11 10 11 9 10 9...
result:
ok 1000 numbers
Test #5:
score: 0
Accepted
time: 7762ms
memory: 175912kb
input:
10000 BG | WB GG | RG YOYYRWOR|OYBRWWRB YRWWRWOO|OOGOWRYB BG | YG BB | YG GB | BY OG | GG RBYWOWRY|RYROYOBW ORGBWBYY|ORBWROWW WO | YG GR | BG YB | YW BO | WW RWRYGOWB|BBORBGRO WG...
output:
2 10 7 10 10 9 11 10 12 11 9 10 10 12 10 11 11 10 12 12 10 11 10 11 12 10 10 10 11 9 12 9 10 10 10 11 12 12 11 11 10 11 9 11 8 11 11 12 13 10 10 12 11 10 11 11 11 10 12 10 11 12 11 11 11 11 10 10 10 11 12 12 11 11 11 11 11 12 10 12 11 8 11 12 10 11 11 11 12 11 10 11 12 10 9 9 9 11 11 11 10 11 9 10 9...
result:
ok 10000 numbers
Test #6:
score: 0
Accepted
time: 8602ms
memory: 175876kb
input:
100000 BG | WB GG | RG YOYYRWOR|OYBRWWRB YRWWRWOO|OOGOWRYB BG | YG BB | YG GB | BY OG | GG RBYWOWRY|RYROYOBW ORGBWBYY|ORBWROWW WO | YG GR | BG YB | YW BO | WW RWRYGOWB|BBORBGRO W...
output:
2 10 7 10 10 9 11 10 12 11 9 10 10 12 10 11 11 10 12 12 10 11 10 11 12 10 10 10 11 9 12 9 10 10 10 11 12 12 11 11 10 11 9 11 8 11 11 12 13 10 10 12 11 10 11 11 11 10 12 10 11 12 11 11 11 11 10 10 10 11 12 12 11 11 11 11 11 12 10 12 11 8 11 12 10 11 11 11 12 11 10 11 12 10 9 9 9 11 11 11 10 11 9 10 9...
result:
ok 100000 numbers
Extra Test:
score: 0
Extra Test Passed