Run Code
|
API
|
Code Wall
|
Users
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
an awesome question of basic graph traversal (786A)
Language:
Ada
Assembly
Bash
C#
C++ (gcc)
C++ (clang)
C++ (vc++)
C (gcc)
C (clang)
C (vc)
Client Side
Clojure
Common Lisp
D
Elixir
Erlang
F#
Fortran
Go
Haskell
Java
Javascript
Kotlin
Lua
MySql
Node.js
Ocaml
Octave
Objective-C
Oracle
Pascal
Perl
Php
PostgreSQL
Prolog
Python
Python 3
R
Rust
Ruby
Scala
Scheme
Sql Server
Swift
Tcl
Visual Basic
Layout:
Vertical
Horizontal
#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; }
g++
8 4 6 2 3 4 2 3 6
Show compiler warnings
[
+
] Compiler args
[
-
]
Show input
Compilation time: 1.74 sec, absolute running time: 0.15 sec, cpu time: 0.07 sec, memory peak: 3 Mb, absolute service time: 1,89 sec
edit mode
|
history
|
discussion
Win Win Win Win Win Win Win Lose Win Lose Lose Win Lose Lose