oj.uz

답안 #833422

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
833422 2023-08-22T05:30:05 Z rahulverma 아름다운 순열 (IZhO12_beauty) Java 11
0 / 100
 3000 ms 225904 KB 
import java.util.*;

public class beauty {
    static long[] a = new long[100];
    static long[] b = new long[100];
    static long[][] dp = new long[1 << 20][23];
    static int n;

    static long rec(long mask, int last) {
        if (mask == (pow(n) - 1)) return 1;

        if (last != -1 && dp[(int) mask][last] != -1) return dp[(int) mask][last];
        long an = 0;
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) == 0) {
                if (last == -1 || a[(int) last] == a[i] || b[(int) last] == b[i]) {
                    an += rec(mask | pow(i), i);
                }
            }
        }
        if(last != -1)dp[(int) mask][last] = an;
        return an;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int i;
        long ans = 0;

        n = scanner.nextInt();

        for (i = 0; i < n; i++) {
            long p = scanner.nextLong();
            a[i] = Long.bitCount(p);
            long p1 = p;
            while (p1 > 0) {
                if (p1 % 3 == 1) b[i]++;
                p1 /= 3;
            }
        }
        for (i = 0; i < pow(20); i++) {
            Arrays.fill(dp[i], -1);
        }
        ans += rec(0, -1);

        System.out.println(ans);
    }
    public static long pow(int i) {
    	long ans = 1;
    	while(i > 0) {
    		ans *= 2;
    		i--;
    	}
    	return ans;
    }
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 387 ms 223608 KB Output is correct
2 Correct 395 ms 223592 KB Output is correct
3 Correct 367 ms 223580 KB Output is correct
4 Correct 383 ms 223556 KB Output is correct
5 Correct 415 ms 223536 KB Output is correct
6 Correct 393 ms 225488 KB Output is correct
7 Correct 413 ms 225532 KB Output is correct
8 Correct 407 ms 225204 KB Output is correct
9 Correct 378 ms 225532 KB Output is correct
10 Correct 383 ms 225432 KB Output is correct
11 Correct 395 ms 225340 KB Output is correct
12 Correct 414 ms 225824 KB Output is correct
13 Correct 487 ms 225820 KB Output is correct
14 Correct 830 ms 225408 KB Output is correct
15 Correct 868 ms 225376 KB Output is correct
16 Correct 736 ms 225904 KB Output is correct
17 Correct 874 ms 225404 KB Output is correct
18 Correct 732 ms 225888 KB Output is correct
19 Execution timed out 3039 ms 225284 KB Time limit exceeded
20 Halted 0 ms 0 KB -