Submission #1403734
Source Code Expand
#include <algorithm> #include <bitset> #include <cassert> #include <cctype> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> #define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++) using namespace std; typedef long long int ll; typedef vector<int> VI; typedef vector<ll> VL; typedef pair<int, int> PI; const int inf = 1000; int main(void){ int n; cin >> n; VI a(n); vector<PI> pool; REP(i, 0, n) { cin >> a[i]; pool.push_back(PI(a[i], i)); } sort(pool.begin(), pool.end()); int h, w; cin >> h >> w; vector<VI> b(h, VI(w)); vector<PI> mi(n, PI(inf, inf)), ma(n, PI(-inf, -inf)); REP(i, 0, h) { REP(j, 0, w) { cin >> b[i][j]; int c = b[i][j]; mi[c].first = min(mi[c].first, i); mi[c].second = min(mi[c].second, j); ma[c].first = max(ma[c].first, i); ma[c].second = max(ma[c].second, j); } } assert (n <= 10); // Try all possibilities, O(n!) VI perm(n); REP(i, 0, n) { perm[i] = i; } bool ok = false; do { // This permutation is valid? bool valid = true; if (not valid) { continue; } vector<VI> board(h, VI(w, -1)); vector<VI> order(h, VI(w, -1)); REP(i, 0, n) { int p = perm[i]; int c = pool[i].second; if (not valid) { break; } REP(j, mi[p].first, ma[p].first + 1) { if (not valid) { break; } REP(k, mi[p].second, ma[p].second + 1) { int oldc = order[j][k]; if (oldc >= 0 && a[oldc] == a[c]) { valid = false; break; } board[j][k] = p; order[j][k] = c; } } } if (0) { cerr << "board:" << endl; REP(k, 0, board.size()) { REP(l, 0, board[0].size()) { cerr << " " << board[k][l]; } cerr << endl; } } if (not valid) { continue; } if (board == b) { ok = true; } } while (next_permutation(perm.begin(), perm.end()) && not ok); cout << (ok ? 1 : 0) << endl; }
Submission Info
Submission Time | |
---|---|
Task | D - 天下一芸術 |
User | kobae964 |
Language | C++14 (GCC 5.4.1) |
Score | 35 |
Code Size | 2212 Byte |
Status | RE |
Exec Time | 3155 ms |
Memory | 792 KB |
Judge Result
Set Name | small | medium | All | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 35 / 35 | 0 / 40 | 0 / 35 | ||||||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
small | 00_sample0.txt, 00_sample1.txt, 00_sample2.txt, 00_sample3.txt, 01_manual1.txt, 01_manual2.txt, 01_manual3.txt, 01_manual4.txt, 01_manual5.txt, 01_manual6.txt, 02_small100.txt, 02_small101.txt, 02_small102.txt, 02_small103.txt, 02_small104.txt, 02_small105.txt, 02_small106.txt, 02_small107.txt, 02_small108.txt, 02_small109.txt, 02_small110.txt, 02_small111.txt, 02_small112.txt, 02_small113.txt, 02_small114.txt, 02_small115.txt, 02_small116.txt, 02_small117.txt, 02_small118.txt, 02_small119.txt, 02_small120.txt, 03_small_b1.txt, 03_small_b2.txt, 03_small_b3.txt |
medium | 00_sample0.txt, 00_sample1.txt, 00_sample2.txt, 00_sample3.txt, 01_manual1.txt, 01_manual2.txt, 01_manual3.txt, 01_manual4.txt, 01_manual5.txt, 01_manual6.txt, 02_small100.txt, 02_small101.txt, 02_small102.txt, 02_small103.txt, 02_small104.txt, 02_small105.txt, 02_small106.txt, 02_small107.txt, 02_small108.txt, 02_small109.txt, 02_small110.txt, 02_small111.txt, 02_small112.txt, 02_small113.txt, 02_small114.txt, 02_small115.txt, 02_small116.txt, 02_small117.txt, 02_small118.txt, 02_small119.txt, 02_small120.txt, 03_small_b1.txt, 03_small_b2.txt, 03_small_b3.txt, 11_manual0.txt, 11_manual1.txt, 12_medium100.txt, 12_medium101.txt, 12_medium102.txt, 12_medium103.txt, 12_medium104.txt, 12_medium105.txt, 12_medium106.txt, 12_medium107.txt, 12_medium108.txt, 12_medium109.txt, 12_medium110.txt, 12_medium111.txt, 12_medium112.txt, 12_medium113.txt, 12_medium114.txt, 12_medium115.txt, 12_medium116.txt, 12_medium117.txt, 12_medium118.txt, 12_medium119.txt, 12_medium120.txt, 12_medium121.txt, 12_medium122.txt, 12_medium123.txt, 12_medium124.txt, 12_medium125.txt, 12_medium126.txt, 12_medium127.txt, 12_medium128.txt, 12_medium129.txt |
All | 00_sample0.txt, 00_sample1.txt, 00_sample2.txt, 00_sample3.txt, 01_manual1.txt, 01_manual2.txt, 01_manual3.txt, 01_manual4.txt, 01_manual5.txt, 01_manual6.txt, 02_small100.txt, 02_small101.txt, 02_small102.txt, 02_small103.txt, 02_small104.txt, 02_small105.txt, 02_small106.txt, 02_small107.txt, 02_small108.txt, 02_small109.txt, 02_small110.txt, 02_small111.txt, 02_small112.txt, 02_small113.txt, 02_small114.txt, 02_small115.txt, 02_small116.txt, 02_small117.txt, 02_small118.txt, 02_small119.txt, 02_small120.txt, 03_small_b1.txt, 03_small_b2.txt, 03_small_b3.txt, 11_manual0.txt, 11_manual1.txt, 12_medium100.txt, 12_medium101.txt, 12_medium102.txt, 12_medium103.txt, 12_medium104.txt, 12_medium105.txt, 12_medium106.txt, 12_medium107.txt, 12_medium108.txt, 12_medium109.txt, 12_medium110.txt, 12_medium111.txt, 12_medium112.txt, 12_medium113.txt, 12_medium114.txt, 12_medium115.txt, 12_medium116.txt, 12_medium117.txt, 12_medium118.txt, 12_medium119.txt, 12_medium120.txt, 12_medium121.txt, 12_medium122.txt, 12_medium123.txt, 12_medium124.txt, 12_medium125.txt, 12_medium126.txt, 12_medium127.txt, 12_medium128.txt, 12_medium129.txt, 21_manual0.txt, 21_manual1.txt, 21_manual10.txt, 21_manual11.txt, 21_manual12.txt, 21_manual13.txt, 21_manual2.txt, 21_manual3.txt, 21_manual4.txt, 21_manual5.txt, 21_manual6.txt, 21_manual7.txt, 21_manual8.txt, 21_manual9.txt, 21_manual_L0.txt, 21_manual_L1.txt, 21_manual_L2.txt, 21_manual_L3.txt, 21_manual_L4.txt, 21_manual_L5.txt, 21_manual_L6.txt, 21_manual_L7.txt, 21_manual_L8.txt, 22_hard100.txt, 22_hard101.txt, 22_hard1011.txt, 22_hard102.txt, 22_hard103.txt, 22_hard104.txt, 22_hard105.txt, 22_hard106.txt, 22_hard107.txt, 22_hard108.txt, 22_hard109.txt, 22_hard110.txt, 22_hard111.txt, 22_hard112.txt, 22_hard113.txt, 22_hard114.txt, 22_hard1140.txt, 22_hard115.txt, 22_hard116.txt, 22_hard117.txt, 22_hard118.txt, 22_hard119.txt, 22_hard120.txt, 22_hard121.txt, 22_hard122.txt, 22_hard123.txt, 22_hard124.txt, 22_hard125.txt, 22_hard126.txt, 22_hard127.txt, 22_hard128.txt, 22_hard129.txt, 22_hard130.txt, 22_hard131.txt, 22_hard132.txt, 22_hard133.txt, 22_hard134.txt, 22_hard135.txt, 22_hard154.txt, 22_hard2096.txt, 22_hard275.txt, 22_hard345.txt, 22_hard351.txt, 22_hard437.txt, 22_hard442.txt, 22_hard524.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample0.txt | AC | 1 ms | 256 KB |
00_sample1.txt | AC | 1 ms | 256 KB |
00_sample2.txt | AC | 1 ms | 256 KB |
00_sample3.txt | AC | 1 ms | 256 KB |
01_manual1.txt | AC | 1 ms | 256 KB |
01_manual2.txt | AC | 1 ms | 256 KB |
01_manual3.txt | AC | 1 ms | 256 KB |
01_manual4.txt | AC | 1 ms | 256 KB |
01_manual5.txt | AC | 1 ms | 256 KB |
01_manual6.txt | AC | 1 ms | 256 KB |
02_small100.txt | AC | 1 ms | 256 KB |
02_small101.txt | AC | 1 ms | 256 KB |
02_small102.txt | AC | 1 ms | 256 KB |
02_small103.txt | AC | 1 ms | 256 KB |
02_small104.txt | AC | 1 ms | 256 KB |
02_small105.txt | AC | 1 ms | 256 KB |
02_small106.txt | AC | 1 ms | 256 KB |
02_small107.txt | AC | 1 ms | 256 KB |
02_small108.txt | AC | 1 ms | 256 KB |
02_small109.txt | AC | 1 ms | 256 KB |
02_small110.txt | AC | 1 ms | 256 KB |
02_small111.txt | AC | 1 ms | 256 KB |
02_small112.txt | AC | 1 ms | 256 KB |
02_small113.txt | AC | 1 ms | 256 KB |
02_small114.txt | AC | 1 ms | 256 KB |
02_small115.txt | AC | 1 ms | 256 KB |
02_small116.txt | AC | 1 ms | 256 KB |
02_small117.txt | AC | 1 ms | 256 KB |
02_small118.txt | AC | 1 ms | 256 KB |
02_small119.txt | AC | 1 ms | 256 KB |
02_small120.txt | AC | 1 ms | 256 KB |
03_small_b1.txt | AC | 1 ms | 256 KB |
03_small_b2.txt | AC | 1 ms | 256 KB |
03_small_b3.txt | AC | 1 ms | 256 KB |
11_manual0.txt | AC | 9 ms | 256 KB |
11_manual1.txt | AC | 8 ms | 768 KB |
12_medium100.txt | AC | 61 ms | 604 KB |
12_medium101.txt | AC | 300 ms | 616 KB |
12_medium102.txt | TLE | 3155 ms | 768 KB |
12_medium103.txt | TLE | 3155 ms | 792 KB |
12_medium104.txt | TLE | 3155 ms | 768 KB |
12_medium105.txt | TLE | 3155 ms | 792 KB |
12_medium106.txt | TLE | 3155 ms | 792 KB |
12_medium107.txt | TLE | 3155 ms | 792 KB |
12_medium108.txt | AC | 165 ms | 256 KB |
12_medium109.txt | AC | 2 ms | 256 KB |
12_medium110.txt | TLE | 3155 ms | 760 KB |
12_medium111.txt | TLE | 3155 ms | 792 KB |
12_medium112.txt | TLE | 3155 ms | 792 KB |
12_medium113.txt | TLE | 3155 ms | 792 KB |
12_medium114.txt | TLE | 3155 ms | 512 KB |
12_medium115.txt | TLE | 3155 ms | 784 KB |
12_medium116.txt | TLE | 3155 ms | 792 KB |
12_medium117.txt | TLE | 3155 ms | 256 KB |
12_medium118.txt | AC | 1 ms | 256 KB |
12_medium119.txt | AC | 699 ms | 256 KB |
12_medium120.txt | TLE | 3155 ms | 648 KB |
12_medium121.txt | TLE | 3155 ms | 760 KB |
12_medium122.txt | AC | 42 ms | 740 KB |
12_medium123.txt | TLE | 3155 ms | 792 KB |
12_medium124.txt | AC | 8 ms | 768 KB |
12_medium125.txt | AC | 66 ms | 768 KB |
12_medium126.txt | AC | 21 ms | 256 KB |
12_medium127.txt | AC | 1 ms | 256 KB |
12_medium128.txt | TLE | 3155 ms | 772 KB |
12_medium129.txt | AC | 6 ms | 640 KB |
21_manual0.txt | RE | 97 ms | 256 KB |
21_manual1.txt | RE | 97 ms | 256 KB |
21_manual10.txt | RE | 96 ms | 256 KB |
21_manual11.txt | RE | 97 ms | 256 KB |
21_manual12.txt | RE | 96 ms | 256 KB |
21_manual13.txt | RE | 98 ms | 256 KB |
21_manual2.txt | RE | 96 ms | 256 KB |
21_manual3.txt | RE | 98 ms | 256 KB |
21_manual4.txt | RE | 99 ms | 256 KB |
21_manual5.txt | RE | 100 ms | 256 KB |
21_manual6.txt | RE | 97 ms | 256 KB |
21_manual7.txt | RE | 96 ms | 256 KB |
21_manual8.txt | RE | 96 ms | 256 KB |
21_manual9.txt | RE | 98 ms | 256 KB |
21_manual_L0.txt | RE | 96 ms | 256 KB |
21_manual_L1.txt | RE | 103 ms | 384 KB |
21_manual_L2.txt | RE | 103 ms | 384 KB |
21_manual_L3.txt | RE | 105 ms | 384 KB |
21_manual_L4.txt | RE | 103 ms | 384 KB |
21_manual_L5.txt | RE | 104 ms | 384 KB |
21_manual_L6.txt | RE | 106 ms | 384 KB |
21_manual_L7.txt | RE | 105 ms | 384 KB |
21_manual_L8.txt | RE | 105 ms | 384 KB |
22_hard100.txt | RE | 101 ms | 384 KB |
22_hard101.txt | TLE | 3155 ms | 620 KB |
22_hard1011.txt | RE | 103 ms | 384 KB |
22_hard102.txt | RE | 103 ms | 384 KB |
22_hard103.txt | RE | 104 ms | 384 KB |
22_hard104.txt | RE | 102 ms | 384 KB |
22_hard105.txt | RE | 105 ms | 384 KB |
22_hard106.txt | RE | 104 ms | 384 KB |
22_hard107.txt | RE | 108 ms | 384 KB |
22_hard108.txt | RE | 97 ms | 256 KB |
22_hard109.txt | RE | 100 ms | 256 KB |
22_hard110.txt | RE | 104 ms | 384 KB |
22_hard111.txt | RE | 102 ms | 384 KB |
22_hard112.txt | RE | 103 ms | 384 KB |
22_hard113.txt | RE | 104 ms | 384 KB |
22_hard114.txt | RE | 104 ms | 384 KB |
22_hard1140.txt | RE | 98 ms | 256 KB |
22_hard115.txt | RE | 105 ms | 384 KB |
22_hard116.txt | RE | 100 ms | 256 KB |
22_hard117.txt | RE | 100 ms | 256 KB |
22_hard118.txt | RE | 104 ms | 384 KB |
22_hard119.txt | RE | 103 ms | 384 KB |
22_hard120.txt | RE | 104 ms | 384 KB |
22_hard121.txt | RE | 104 ms | 384 KB |
22_hard122.txt | RE | 100 ms | 256 KB |
22_hard123.txt | RE | 99 ms | 256 KB |
22_hard124.txt | RE | 97 ms | 256 KB |
22_hard125.txt | RE | 98 ms | 256 KB |
22_hard126.txt | RE | 100 ms | 256 KB |
22_hard127.txt | RE | 105 ms | 384 KB |
22_hard128.txt | RE | 104 ms | 384 KB |
22_hard129.txt | RE | 111 ms | 384 KB |
22_hard130.txt | RE | 102 ms | 384 KB |
22_hard131.txt | RE | 104 ms | 384 KB |
22_hard132.txt | RE | 97 ms | 256 KB |
22_hard133.txt | RE | 98 ms | 256 KB |
22_hard134.txt | RE | 104 ms | 384 KB |
22_hard135.txt | RE | 107 ms | 384 KB |
22_hard154.txt | RE | 105 ms | 384 KB |
22_hard2096.txt | RE | 100 ms | 256 KB |
22_hard275.txt | RE | 105 ms | 384 KB |
22_hard345.txt | RE | 100 ms | 256 KB |
22_hard351.txt | RE | 100 ms | 256 KB |
22_hard437.txt | RE | 104 ms | 384 KB |
22_hard442.txt | RE | 105 ms | 384 KB |
22_hard524.txt | RE | 105 ms | 384 KB |