Submission #2139909

Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

//#define int long long
#define reps(i,s,n) for(int (i)=(s);(i)<(int)(n);++(i))
#define rep(i,n) reps(i,0,n)
#define rept(i,n) reps(i,0,((n)+1))
#define repst(i,s,n) reps(i,s,((n)+1))
#define reprt(i,n,t) for(ll (i)=(n);(i)>=(t);--(i))
#define repr(i,n) reprt(i,n,0)
#define each(itr,v) for(auto &(itr):(v))
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define tmax(x,y,z) max(x,max(y,z))
#define tmin(x,y,z) min(x,min(y,z))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln '\n'
#define dbg(x) cout<<#x" = "<<(x)<<ln
#define dbga(x,n) {cout<<#x" : ";for(int (i)=0;i<(n);++i){cout<<((x)[i])<<(i==((n)-1)?'\n':' ');}}

typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vld;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vector<int> > mat;

const ll inf = (ll)1e9+10;
const ll linf = (ll)1e18+10;
const ll mod = (ll)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};
const double eps = 1e-10;

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ━━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…
// .。.:( ^ω^)・゚+.。.:( ^ω^)・゚+.。.:( ^ω^)・゚+.。.:( ^ω^)・゚+.。.:( ^ω^)・゚+
// ・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・

// 2部グラフの完全マッチングの偶奇を求める問題
// 隣接行列Gの完全マッチングの個数はperm(G)に等しいらしい perm(G)を多項式時間で求めるアルゴリズムは存在しないらしい
// 偶奇が知りたいだけなら符号を無視できるから結局det(G)%2を求めるだけでいい

int n;
string s;

// N*Nの行列Mの行列式を求める
int det(mat &M) {
	int n = M.size(), res = 1;
	rep(i,n) {
		reps(j,i+1,n) {
			for (; M[j][i] != 0; res = -res) {
				int r = M[i][i] / M[j][i];
				reps(k, i, n) {
					int t = M[i][k] - r * M[j][k];
					M[i][k] = M[j][k], M[j][k] = t;
				}
			}
		}
		res *= M[i][i];
	}
	return res;
}

signed main() {
	cin >> n;
	mat m(n,vi(n,0));
	rep(i,n) {
		cin >> s;
		rep(j,n) m[i][j] = s[j]-'0';
	}
	cout << (det(m)%2 ? "Odd" : "Even") << ln;
}

Submission Info

Submission Time
Task C - 鯛焼き
User creep04
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2870 Byte
Status
Exec Time 7 ms
Memory 384 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All 100 / 100 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
Case Name Status Exec Time Memory
01.txt 1 ms 256 KB
02.txt 1 ms 256 KB
03.txt 1 ms 256 KB
04.txt 1 ms 256 KB
05.txt 1 ms 256 KB
06.txt 1 ms 256 KB
07.txt 1 ms 256 KB
08.txt 1 ms 256 KB
09.txt 1 ms 256 KB
10.txt 1 ms 256 KB
11.txt 1 ms 256 KB
12.txt 1 ms 256 KB
13.txt 1 ms 256 KB
14.txt 1 ms 256 KB
15.txt 1 ms 256 KB
16.txt 1 ms 256 KB
17.txt 1 ms 256 KB
18.txt 1 ms 256 KB
19.txt 1 ms 256 KB
20.txt 1 ms 256 KB
21.txt 7 ms 384 KB
22.txt 7 ms 384 KB
23.txt 7 ms 384 KB
24.txt 7 ms 384 KB
25.txt 7 ms 384 KB
26.txt 7 ms 384 KB
27.txt 7 ms 384 KB
28.txt 7 ms 384 KB
29.txt 7 ms 384 KB
30.txt 7 ms 384 KB
31.txt 7 ms 384 KB
32.txt 7 ms 384 KB
33.txt 7 ms 384 KB
34.txt 7 ms 384 KB
35.txt 1 ms 384 KB
36.txt 1 ms 384 KB
37.txt 1 ms 384 KB
38.txt 1 ms 384 KB
39.txt 1 ms 384 KB
40.txt 1 ms 384 KB
41.txt 1 ms 384 KB
42.txt 1 ms 384 KB
43.txt 1 ms 384 KB
44.txt 1 ms 384 KB
45.txt 1 ms 384 KB
46.txt 1 ms 384 KB
47.txt 1 ms 256 KB
48.txt 1 ms 256 KB
49.txt 1 ms 256 KB
50.txt 1 ms 256 KB
51.txt 1 ms 256 KB
52.txt 1 ms 256 KB
53.txt 1 ms 256 KB
54.txt 1 ms 256 KB
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB
sample_04.txt 1 ms 256 KB