QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#373826#2047. Dice PuzzleKKT89100 ✓11ms3936kbC++172.3kb2024-04-02 07:52:552024-04-02 07:52:57

Judging History

This is the latest submission verdict.

  • [2024-04-02 07:52:57]
  • Judged
  • Verdict: 100
  • Time: 11ms
  • Memory: 3936kb
  • [2024-04-02 07:52:55]
  • Submitted

answer

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}

int d[24][3]={
    {6,2,3},
    {1,5,3},
    {1,2,4},
    {6,5,4},
    {1,3,2},
    {6,4,2},
    {6,3,5},
    {1,4,5},
    {2,1,3},
    {5,6,3},
    {5,1,4},
    {2,6,4},
    {5,3,1},
    {2,4,1},
    {2,3,6},
    {5,4,6},
    {4,1,2},
    {3,6,2},
    {3,1,5},
    {4,6,5},
    {3,2,1},
    {4,5,1},
    {4,2,6},
    {3,5,6},
};

int T[3][3],F[3][3];

int A[3][3][3];

vector<int> v;

void dfs(int num){
    if(num==27){
        int sum=0;
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                sum+=(7-d[A[i][j][2]][2]);
            }
        }
        v.push_back(sum);
        return;
    }
    int i=num/9,j=num/3%3,k=num%3;
    for(int id=0;id<24;id++){
        A[i][j][k]=id;
        // ここで判定を書く
        if(i==0){
            if(T[j][k]!=0 and T[j][k]!=d[id][0])continue;
        }
        if(j==2){
            if(F[i][k]!=0 and F[i][k]!=d[id][1])continue;
        }
        if(i>0){
            int u=A[i-1][j][k];
            if(7-d[u][0]+d[id][0]!=7)continue;
        }
        if(j>0){
            int u=A[i][j-1][k];
            if(d[u][1]+(7-d[id][1])!=7)continue;
        }
        if(k>0){
            int u=A[i][j][k-1];
            if((7-d[u][2])+d[id][2]!=7)continue;
        }
        // OKなら
        dfs(num+1);
    }
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int q; cin >> q;
    while(q--){
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                cin >> T[i][j];
            }
        }
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                cin >> F[i][j];
            }
        }
        v.clear();
        dfs(0);
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()),v.end());
        if(v.size()==0){
            printf("0\n");
        }
        else{
            printf("%d",v[0]);
            for(int i=1;i<v.size();i++){
                printf(" %d",v[i]);
            }
            printf("\n");
        }
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 11ms
memory: 3936kb

input:

12
1 0 0
0 2 0
0 0 0
5 1 2
5 1 2
0 0 0
2 0 0
0 3 0
0 0 0
0 0 0
0 0 0
0 0 0
2 0 0
0 3 0
0 0 0
0 0 0
0 0 0
3 0 1
1 1 1
1 1 1
1 1 1
2 2 2
2 2 2
2 2 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
5 5 5
0 0 6
0 0 6
0 0 0
0 0 0
0 4 0
5 0 5
0 0 0
0 0 6
0 0 0
0 0 0
0 4 0
5 0 5
0 0 5
0 0 6
0 0 0
0 0 0
0 4 0
5 0 5
0 0...

output:

32 33 36
9 21 24 27 28 29 30 31 32 33 34 35 36 39 42 54
0
27
9 12 15 18 21 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 42 45 48 51 54
31 32 33
21 24 27 28 29 30 31 32 33 34 35 36 39 42
21 28 35 42
0
24 39 54
24 29 34 39 54
39 54

result:

ok 12 lines