QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#261640 | #6475. Cunning Friends | illyakr# | WA | 5ms | 3764kb | C++17 | 5.6kb | 2023-11-23 05:13:14 | 2023-11-23 05:13:15 |
Judging History
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'