Submission #1131996
Source Code Expand
#include <algorithm> #include <cassert> #include <cfloat> #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <deque> #include <iomanip> #include <iostream> #include <limits> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <tuple> #include <vector> #define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i)) #define rep(i,n) FOR(i,0,n) #define pb push_back #define all(v) begin(v), end(v) #define debug(x) cerr<< #x <<": "<<x<<endl #define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<vector<int> > vvi; typedef vector<ll> vll; typedef vector<vector<ll> > vvll; template<class T> using vv=vector<vector< T > >; typedef deque<bool> db; typedef deque<db> ddb; #define INF 1e8 int n; vvi board; int cnt; void manipulate(int i, int j) { cnt += 1; vi tmp = board[i]; rep (k, n) { board[k][j] = tmp[k]; } } int main() { scanf("%d", &n); board.assign(n, vi(n, 0)); db exist_j(n, false); bool impossible = true; vi filled_i(n, 0); rep (i, n) { char tmp; rep (j, n) { scanf(" %c", &tmp); if (tmp == '#') { board[i][j] = 1; exist_j[j] = true; filled_i[i] += 1; impossible = false; } } } if (impossible) { printf("-1\n"); return 0; } vi needed_to_fill(n, 0); rep (i, n) { if (filled_i[i] == n) { continue; } if (exist_j[i]) { needed_to_fill[i] = n - filled_i[i]; continue; } needed_to_fill[i] = n - filled_i[i] + 1; } int min_row = 0; rep (i, n) { if (needed_to_fill[min_row] > needed_to_fill[i]) { min_row = i; } } cnt = 0; if (!exist_j[min_row]) { rep (i, n) { rep (j, n) { if (board[i][j] == 1) { manipulate(i, min_row); i = n; break; } } } } if (board[min_row][min_row] == 0) { int dup_from = 0; rep (i, n) { if (board[i][min_row] == 1) { dup_from = i; break; } } manipulate(dup_from, min_row); } rep (j, n) { if (board[min_row][j] == 0) { manipulate(min_row, j); } } rep (j, n) { rep (i, n) { if (board[i][j] == 1) { continue; } manipulate(min_row, j); break; } } printf("%d\n", cnt); return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Row to Column |
User | tspcx |
Language | C++14 (Clang 3.8.0) |
Score | 1300 |
Code Size | 2634 Byte |
Status | AC |
Exec Time | 16 ms |
Memory | 1280 KB |
Judge Result
Set Name | Sample | Subtask | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 300 / 300 | 1000 / 1000 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt |
Subtask | 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt |
All | 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt, 2_13.txt, 2_14.txt, 2_15.txt, 2_16.txt, 2_17.txt, 2_18.txt, 2_19.txt, 2_20.txt, 2_21.txt, 2_22.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_00.txt | AC | 5 ms | 888 KB |
0_01.txt | AC | 1 ms | 256 KB |
0_02.txt | AC | 1 ms | 256 KB |
0_03.txt | AC | 1 ms | 256 KB |
0_04.txt | AC | 1 ms | 256 KB |
1_00.txt | AC | 1 ms | 256 KB |
1_01.txt | AC | 1 ms | 256 KB |
1_02.txt | AC | 1 ms | 256 KB |
1_03.txt | AC | 1 ms | 256 KB |
1_04.txt | AC | 1 ms | 256 KB |
1_05.txt | AC | 1 ms | 256 KB |
1_06.txt | AC | 1 ms | 256 KB |
1_07.txt | AC | 1 ms | 256 KB |
1_08.txt | AC | 1 ms | 256 KB |
1_09.txt | AC | 1 ms | 256 KB |
1_10.txt | AC | 1 ms | 256 KB |
1_11.txt | AC | 1 ms | 256 KB |
1_12.txt | AC | 1 ms | 256 KB |
1_13.txt | AC | 1 ms | 256 KB |
1_14.txt | AC | 1 ms | 256 KB |
2_00.txt | AC | 14 ms | 1280 KB |
2_01.txt | AC | 14 ms | 1280 KB |
2_02.txt | AC | 15 ms | 1280 KB |
2_03.txt | AC | 16 ms | 1280 KB |
2_04.txt | AC | 15 ms | 1280 KB |
2_05.txt | AC | 15 ms | 1280 KB |
2_06.txt | AC | 15 ms | 1280 KB |
2_07.txt | AC | 11 ms | 896 KB |
2_08.txt | AC | 15 ms | 1280 KB |
2_09.txt | AC | 15 ms | 1152 KB |
2_10.txt | AC | 15 ms | 1152 KB |
2_11.txt | AC | 15 ms | 1280 KB |
2_12.txt | AC | 15 ms | 1152 KB |
2_13.txt | AC | 13 ms | 1024 KB |
2_14.txt | AC | 14 ms | 1152 KB |
2_15.txt | AC | 13 ms | 1024 KB |
2_16.txt | AC | 13 ms | 1152 KB |
2_17.txt | AC | 12 ms | 1024 KB |
2_18.txt | AC | 10 ms | 896 KB |
2_19.txt | AC | 14 ms | 1152 KB |
2_20.txt | AC | 10 ms | 896 KB |
2_21.txt | AC | 9 ms | 896 KB |
2_22.txt | AC | 14 ms | 1280 KB |