oj.uz

Submission #620742

# Submission time Handle Problem Language Result Execution time Memory
620742 2022-08-03T08:41:44 Z 반딧불(#8518) Ruins 3 (JOI20_ruins3) C++17
0 / 100
 6000 ms 45424 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD = 1000000007;

int n;
bool used[30];
int pow3[20];
bool alive[2000002][13];
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;
}

void isAble(int b){
    priority_queue<int> pq;
    vector<int> l1(n), l2(n);
    int rb=b;
    for(int i=0; i<n; i++){
        if(b%3) l1[i]=2;
        if(b%3==2) l2[i]=2;
        b/=3;
    }

    for(int i=0; i<n; i++){ /// i�� �õ��� ����
        int c[3]={0,0,0};
        if(l1[i] == 0) l1[i] = 1;
        else if(l2[i] == 0) l2[i] = 1;
        else continue;
        for(int j=0; j<n; j++){
            c[l1[j]]++, c[l2[j]]++;
            if(c[2]) c[2]--;
            else if(c[1]) c[1]--;
            else c[0]--;
        }
        if(c[1]) alive[rb][i] = 1;

        if(l2[i] == 1) l2[i] = 0;
        else l1[i] = 0;
    }
}

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

    for(int i=0; i<pow3[n]; i++){
        isAble(i);
    }

    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] != alive[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:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
ruins3.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 5897 ms 45424 KB Output is correct
3 Execution timed out 6023 ms 45396 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 5897 ms 45424 KB Output is correct
3 Execution timed out 6023 ms 45396 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 5897 ms 45424 KB Output is correct
3 Execution timed out 6023 ms 45396 KB Time limit exceeded
4 Halted 0 ms 0 KB -