QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#590494#9304. Sean the CubersparkuggzAC ✓10287ms176092kbC++147.2kb2024-09-26 01:02:122024-09-26 01:02:12

Judging History

This is the latest submission verdict.

  • [2024-09-26 01:02:12]
  • Judged
  • Verdict: AC
  • Time: 10287ms
  • Memory: 176092kb
  • [2024-09-26 01:02:12]
  • Submitted

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,我给组数据试试?

详细

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