Submission #2206300
Source Code Expand
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> int descending_compare(const void *a, const void *b){ if (*(int*)a > *(int*)b){ return -1; }else if (*(int*)a == *(int*)b){ return 0; }else{ return 1; } } int ascending_compare(const void *a, const void *b){ if (*(int*)a < *(int*)b){ return -1; }else if (*(int*)a == *(int*)b){ return 0; }else{ return 1; } } // array pointer = *a, num of element = n, key key int lower_bound(int *a, int n, int key){ int ng, mid, ok; ng = -1, ok = n-1; while (abs(ok - ng) > 1){ mid = (ok + ng) / 2; if (key <= a[mid]){ ok = mid; }else{ ng = mid; } } if (a[ok] >= key)return ok; return n; } //greatest common divisor unsigned long gcd(unsigned long x, unsigned long y){ if (y == 0){ return x; }else if (x > y){ return gcd(y, x % y); }else{ return gcd(x, y % x); } } unsigned long lcm(unsigned long x, unsigned long y){ unsigned long g = gcd(x, y); return x*y/g; } long long factorial(int x){ long long rtn = 1; int i; for (i = x; i > 1; i--){ rtn = (rtn*i); } return rtn; } /*unsigned long long pascal[100][100] = {0}; void make_pascal(void){ for (int i = 0; i < 100; i++){ pascal[i][0] = 1; } pascal[1][1] = 1; for (int i = 2; i < 100; i++){ for (int j = 1; j < 100; j++){ pascal[i][j] = (pascal[i-1][j-1]+pascal[i-1][j]) % mod; } } }*/ long long mod = 1000000007; //x ^ n long long mod_pow(long long x, long long n){ long long res = 1; for(int i = 0;i < 60; i++){ if(n >> i & 1) res = res * x % mod; x = x * x % mod; } return res; } /*int struct_ascending_compare(const void *p, const void *q) { return ((structname*)p)->member - ((strcutname*)q)->member; }*/ int field[3][3]; int tate[3][2]; int yoko[2][3]; int total; int dfs(int level){ int chokudai = 0; if (level == 9){ for (int i = 0; i < 3; i++){ for (int j = 0; j < 2; j++){ if (field[i][j] == field[i][j+1]){ chokudai += tate[i][j]; } } } for (int i = 0; i < 2; i++){ for (int j = 0; j < 3; j++){ if (field[i][j] == field[i+1][j]){ chokudai += yoko[i][j]; } } } return chokudai; } //空いているマスにlevelに応じて書き込む int tmp; int max = -1; int min = total + 1; for (int i = 0; i < 3; i++){ for (int j = 0; j < 3; j++){ if (field[i][j] == 0){ if (level % 2){ field[i][j] = -1; tmp = dfs(level+1); field[i][j] = 0; min = min>tmp?tmp:min; }else{ field[i][j] = 1; tmp = dfs(level+1); field[i][j] = 0; max = max<tmp?tmp:max; } } } } if (level % 2){ return min; }else{ return max; } } int main(void){ for (int j = 0; j < 2; j++){ for (int i = 0; i < 3; i++){ scanf("%d", &tate[i][j]); total += tate[i][j]; } } for (int j = 0; j < 3; j++){ for (int i = 0; i < 2; i++){ scanf("%d", &yoko[i][j]); total += yoko[i][j]; } } int chokudai = dfs(0); int chokuko = total - chokudai; printf("%d\n%d\n", chokudai, chokuko); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 双子と○×ゲーム |
User | Morifo |
Language | C (Clang 3.8.0) |
Score | 100 |
Code Size | 3909 Byte |
Status | AC |
Exec Time | 27 ms |
Memory | 128 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample-01.txt, sample-02.txt |
All | sample-01.txt, sample-02.txt, test-01.txt, test-02.txt, test-03.txt, test-04.txt, test-05.txt, test-06.txt, test-07.txt, test-08.txt, test-09.txt, test-10.txt, test-11.txt, test-12.txt, test-13.txt, test-14.txt, test-15.txt, test-16.txt, test-17.txt, test-18.txt, test-19.txt, test-20.txt, sample-01.txt, sample-02.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample-01.txt | AC | 27 ms | 128 KB |
sample-02.txt | AC | 27 ms | 128 KB |
test-01.txt | AC | 27 ms | 128 KB |
test-02.txt | AC | 27 ms | 128 KB |
test-03.txt | AC | 27 ms | 128 KB |
test-04.txt | AC | 27 ms | 128 KB |
test-05.txt | AC | 27 ms | 128 KB |
test-06.txt | AC | 27 ms | 128 KB |
test-07.txt | AC | 27 ms | 128 KB |
test-08.txt | AC | 27 ms | 128 KB |
test-09.txt | AC | 27 ms | 128 KB |
test-10.txt | AC | 27 ms | 128 KB |
test-11.txt | AC | 27 ms | 128 KB |
test-12.txt | AC | 27 ms | 128 KB |
test-13.txt | AC | 27 ms | 128 KB |
test-14.txt | AC | 27 ms | 128 KB |
test-15.txt | AC | 27 ms | 128 KB |
test-16.txt | AC | 27 ms | 128 KB |
test-17.txt | AC | 27 ms | 128 KB |
test-18.txt | AC | 27 ms | 128 KB |
test-19.txt | AC | 27 ms | 128 KB |
test-20.txt | AC | 27 ms | 128 KB |