oj.uz

답안 #620661

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
620661 2022-08-03T07:58:17 Z 반딧불(#8518) 유적 3 (JOI20_ruins3) C++17
0 / 100
 6000 ms 19016 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD = 1000000007;

int n;
bool used[30];
int pow3[20];
int able[2000002]; /// state = x�� �� ��ġ ������ �ִ�
ll DP[2][2000002];

inline int bit(int x, int k){
    return (x/pow3[k])%3;
}

void init(){
    pow3[0] = 1;
    for(int i=1; i<=13; i++) pow3[i] = pow3[i-1] * 3;

    for(int i=0; i<pow3[n]; i++){
        able[i] = n;
        for(int j=n-1; j>=0; j--){
            if(!bit(i, j)) break;
            able[i]--;
        }
    }
}

bool isAble(int b, int x){
    int rb=b;
    vector<int> vec;
    for(int i=0; i<n; i++){
        for(int j=b%3; j<(i==x?1:2); j++) vec.push_back(i);
        b/=3;
    }
    int p=(int)vec.size();
    vec.push_back(x);
    b=rb;
    for(int i=0; i<n; i++){
        for(int j=0; j<b%3; j++) vec.push_back(i);
        b/=3;
    }

    for(int t=1; t<=n; t++){
        vector<bool> mark(n);
        vector<int> newVec;
        for(auto x: vec){
            if(x>=0 && mark[x]) newVec.push_back(x-1);
            else newVec.push_back(x);
            if(x>=0) mark[x]=1;
        }
        vec.swap(newVec);
    }
    return vec[p] >= 0;
}

int main(){
    scanf("%d", &n);
    init();
    for(int i=1; i<=n; i++){
        int x;
        scanf("%d", &x);
        used[x] = 1;
    }

    DP[0][0] = 1;
    for(int i=1; i<=n*2; i++){ /// i: ����ġ
//        printf("i : %d\n", i);
        int b = i%2;
        for(int j=0; j<pow3[n]; j++) DP[b][j] = 0;
        for(int j=0; j<pow3[n]; j++){ /// j: ����
//            if(j%100==0) printf("j: %d\n", j);
            for(int x=0; x<n; x++){
                if(bit(j, x) == 2) continue; /// �̹� �� ��
                if(used[i] != isAble(j, x)) continue;
                DP[b][j+pow3[x]] = (DP[b][j+pow3[x]] + DP[!b][j]) % MOD;
            }
        }
//        for(int j=0; j<pow3[n]; j++) printf("%d %d: %lld\n", i, j, DP[b][j]);
    }

    printf("%lld", DP[0][pow3[n]-1]);
}

Compilation message

ruins3.cpp: In function 'int main()':
ruins3.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
ruins3.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 6025 ms 19016 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 6025 ms 19016 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 6025 ms 19016 KB Time limit exceeded
3 Halted 0 ms 0 KB -