Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
an awesome question of basic graph traversal (786A)
#include <bits/stdc++.h> using namespace std; #define mp make_pair #define pii pair<int, int> #define pb push_back const int win = 1; const int los = 0; const int act = 3; const int drw = 2; int dp[2][7001], cnt[2][7001], k1, k2, n; vector<int> a, b; void solve(){ queue<pii> q; q.push(mp(1, 0)); dp[0][1] = 0; q.push(mp(1, 1)); dp[1][1] = 0; while(!q.empty()){ int from = q.front().first, chance = q.front().second; q.pop(); int res = dp[chance][from]; const vector<int>& v = (chance == 0)? b : a; for(auto i : v){ int cur = (from - i + n) % n; if(cur == 0) cur = n; if(dp[chance^1][cur] != -1) continue; if(res == los){ //cout << from << " " << chance << " " << cur << " win" << endl; dp[chance^1][cur] = win; q.push(mp(cur, chance^1)); }else{ cnt[chance^1][cur]++; if(cnt[chance^1][cur] == v.size()){ //cout << from << " " << chance << " " << cur << " lose" << endl; dp[chance^1][cur] = los; q.push(mp(cur, chance^1)); } } } } for(int j = 1; j <= n; j++) for(int i = 0; i < 2; i++) if(dp[i][j] == -1) dp[i][j] = 2; } int main(){ ios_base :: sync_with_stdio(0); cin.tie(0); memset(dp, -1, sizeof(dp)); memset(cnt, 0, sizeof(cnt)); cin >> n; cin >> k1; a.resize(k1); for(int j = 0; j < k1; j++) cin >> a[j]; cin >> k2; b.resize(k2); for(int j = 0; j < k2; j++) cin >> b[j]; solve(); //cout << foo(0, 2) << endl; for(int j = 2; j <= n; j++){ int x = dp[0][j]; if(x == win) cout << "Win" << " "; else if(x == los) cout << "Lose" << " "; else cout << "Loop" << " "; //memset(dp, -1, sizeof(dp)); } cout << endl; for(int j = 2; j <= n; j++){ int x = dp[1][j]; if(x == win) cout << "Win" << " "; else if(x == los) cout << "Lose" << " "; else cout << "Loop" << " "; } return 0; }
run
|
edit
|
history
|
help
0
Random Vector Generator
Compare boost optional with the actual value
Search in a rotated sorted array
Procesos estocasticos Beta 2.0
integer division
list
work
Metodos 2- programa3
lifff
strcpy