oj.uz

답안 #833413

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
833413 2023-08-22T05:27:18 Z rahulverma 아름다운 순열 (IZhO12_beauty) Java 11
0 / 100
 379 ms 224720 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);
                }
            }
        }
        return dp[(int) mask][last] = 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, 0);

        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 379 ms 224720 KB Output is correct
2 Correct 374 ms 223696 KB Output is correct
3 Correct 358 ms 223732 KB Output is correct
4 Correct 369 ms 223872 KB Output is correct
5 Incorrect 372 ms 223684 KB Output isn't correct
6 Halted 0 ms 0 KB -