QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#261640#6475. Cunning Friendsillyakr#WA 5ms3764kbC++175.6kb2023-11-23 05:13:142023-11-23 05:13:15

Judging History

你现在查看的是最新测评结果

  • [2023-11-23 05:13:15]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:3764kb
  • [2023-11-23 05:13:14]
  • 提交

answer

#include <bits/stdc++.h>

#pragma GCC optimize("O3")
#define int long long

using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

// whose move, number of stones in piles
map<pair<int, vector<int> >, int> state;

// returns the last player, who loses under current conditions
int rec(int move, vector<int> piles) {
	if (state.find({move, piles}) != state.end())return state[{move, piles}];

	bool empty = true;
	for (int amount : piles) {
		if (amount != 0)empty = false;
	}
	if (empty)return state[{move, piles}] = move;
	for (int& amount : piles) {
		for (int take = 1; take <= amount; take++) {
			amount -= take;
			int last = rec((move + 1) % 3, piles);
			amount += take;

			if (move == 0) {
				// we are playing
				if (last != 0) {
					return state[{move, piles}] = last;
				}
			} else {
				if (last == 0) {
					return state[{move, piles}] = 0;
				}
			}
		}
	}
	return state[{move, piles}] = move;
}

void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++)cin >> a[i];
	sort(a.begin(), a.end());

	if (n == 1) {
		cout << "Win" << endl;return;
	}
	if (n == 2) {
		if (a[0] == 1)cout << "Win" << endl;
		else cout << "Lose" << endl;
		return;
	}
	if (n % 3 == 0) {
		if (a[n - 1] == 1){cout << "Lose" << endl;return;}
		if (a[n - 2] == 1 || a[n - 2] == 2){cout << "Win" << endl;return;}
		cout << "Lose" << endl;
		return;
	}
	if (n % 3 == 1) {
		if (a[n - 2] == 1 || a[n - 2] == 2){cout << "Win" << endl;return;}
		cout << "Lose" << endl;
		return;
	}
	if (n % 3 == 2) {
		if (a[n - 2] == 1){cout << "Win" << endl;return;}
		cout << "Lose" << endl;
		return;
	}
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	solve();
	return 0;
	for (int n_piles = 9; n_piles <= 9; n_piles++) {
		map<int, int> cnt_sol;
		if (n_piles == 1) {
			for (int i = 1; i <= 10; i++) {
				vector<int> piles = {i};
				int res = rec(0, piles);
				cnt_sol[res]++;
			}
		} else if (n_piles == 2) {
			for (int i = 1; i <= 10; i++)for (int j = 1; j <= 10; j++) {
				vector<int> piles = {i, j};
				int res = rec(0, piles);
				cnt_sol[res]++;
				if (res != 0) {
					for (auto q : piles)
						cout << q << " ";
					cout << endl;
				}
			}
		} else if (n_piles == 3) {
			for (int i = 1; i <= 10; i++)for (int j = i; j <= 10; j++)for (int k = j; k <= 10; k++) {
				vector<int> piles = {i, j, k};
				int res = rec(0, piles);
				cnt_sol[res]++;
				if (res != 0) {
					for (auto q : piles)
						cout << q << " ";
					cout << endl;
				}
			}
		} else if (n_piles == 4) {
			for (int i = 1; i <= 10; i++)for (int j = i; j <= 10; j++)for (int k = j; k <= 10; k++)for (int i1 = k; i1 <= 10; i1++) {
				vector<int> piles = {i, j, k, i1};
				int res = rec(0, piles);
				cnt_sol[res]++;
				if (res != 0) {
					for (auto q : piles)
						cout << q << " ";
					cout << endl;
				}
			}
		} else if (n_piles == 5) {
			for (int i = 1; i <= 10; i++)for (int j = i; j <= 10; j++)for (int k = j; k <= 10; k++)for (int i1 = k; i1 <= 10; i1++)for (int i2 = i1; i2 <= 10; i2++) {
				vector<int> piles = {i, j, k, i1, i2};
				int res = rec(0, piles);
				cnt_sol[res]++;
				if (res != 0) {
					for (auto q : piles)
						cout << q << " ";
					cout << endl;
				}
			}
		} else if (n_piles == 6) {
			for (int i = 1; i <= 10; i++)for (int j = i; j <= 10; j++)for (int k = j; k <= 10; k++)for (int i1 = k; i1 <= 10; i1++)for (int i2 = i1; i2 <= 10; i2++)for (int i3 = i2; i3 <= 10; i3++) {
				vector<int> piles = {i, j, k, i1, i2, i3};
				int res = rec(0, piles);
				cnt_sol[res]++;
				if (res != 0) {
					for (auto q : piles)
						cout << q << " ";
					cout << endl;
				}
			}
		} else if (n_piles == 7) {
			for (int i = 1; i <= 10; i++)for (int j = i; j <= 10; j++)for (int k = j; k <= 10; k++)for (int i1 = k; i1 <= 10; i1++)for (int i2 = i1; i2 <= 10; i2++)for (int i3 = i2; i3 <= 10; i3++)for (int i4 = i3; i4 <= 10; i4++) {
				vector<int> piles = {i, j, k, i1, i2, i3, i4};
				int res = rec(0, piles);
				cnt_sol[res]++;
				if (res != 0) {
					for (auto q : piles)
						cout << q << " ";
					cout << endl;
				}
			}
		} else if (n_piles == 8) {
			for (int i = 1; i <= 10; i++)for (int j = i; j <= 10; j++)for (int k = j; k <= 10; k++)for (int i1 = k; i1 <= 10; i1++)for (int i2 = i1; i2 <= 10; i2++)for (int i3 = i2; i3 <= 10; i3++)for (int i4 = i3; i4 <= 10; i4++)for (int i5 = i4; i5 <= 10; i5++) {
				vector<int> piles = {i, j, k, i1, i2, i3, i4, i5};
				int res = rec(0, piles);
				cnt_sol[res]++;
				if (res != 0) {
					for (auto q : piles)
						cout << q << " ";
					cout << endl;
				}
			}
		} else if (n_piles == 9) {
			for (int i = 1; i <= 10; i++)for (int j = i; j <= 10; j++)for (int k = j; k <= 10; k++)for (int i1 = k; i1 <= 10; i1++)for (int i2 = i1; i2 <= 10; i2++)for (int i3 = i2; i3 <= 10; i3++)for (int i4 = i3; i4 <= 10; i4++)for (int i5 = i4; i5 <= 10; i5++)for (int i6 = i5; i6 <= 10; i6++) {
				vector<int> piles = {i, j, k, i1, i2, i3, i4, i5, i6};
				int res = rec(0, piles);
				cnt_sol[res]++;
				if (res != 0) {
					for (auto q : piles)
						cout << q << " ";
					cout << endl;
				}
			}
		}
		cout << n_piles << " -- ";
		for (auto [i, j] : cnt_sol)cout << "(" << i << " - " << j << ")" << "  ";
		cout << endl;
	}
	// cout << rec(0, {2, 2, 1}) << endl;
	// cout << rec(0, {4, 7}) << endl;
}

/*
1 -- (1 - 10)  
2 -- (0 - 81)  (1 - 19)  
3 -- (0 - 922)  (1 - 78)  
4 -- (0 - 9861)  (1 - 139) 
*/

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3404kb

input:

3
2 2 1

output:

Win

result:

ok single line: 'Win'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3468kb

input:

2
4 7

output:

Lose

result:

ok single line: 'Lose'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3476kb

input:

1
1

output:

Win

result:

ok single line: 'Win'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3404kb

input:

2
1 1

output:

Win

result:

ok single line: 'Win'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3384kb

input:

3
1 1 1

output:

Lose

result:

ok single line: 'Lose'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3384kb

input:

4
1 7 1 1

output:

Win

result:

ok single line: 'Win'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3396kb

input:

3
4 7 1

output:

Lose

result:

ok single line: 'Lose'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3408kb

input:

3
2 7 1

output:

Win

result:

ok single line: 'Win'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3492kb

input:

2
2 2

output:

Lose

result:

ok single line: 'Lose'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3476kb

input:

2
1 2

output:

Win

result:

ok single line: 'Win'

Test #11:

score: 0
Accepted
time: 5ms
memory: 3764kb

input:

94251
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

Win

result:

ok single line: 'Win'

Test #12:

score: -100
Wrong Answer
time: 0ms
memory: 3416kb

input:

3
2 2 2

output:

Win

result:

wrong answer 1st lines differ - expected: 'Lose', found: 'Win'