QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#177572 | #7180. Forward-Capturing Pawns | ucup-team859 | TL | 0ms | 0kb | C++14 | 8.8kb | 2023-09-13 04:31:33 | 2023-09-13 04:31:34 |
answer
// C++ includes used for precompiling -*- C++ -*-
// Copyright (C) 2003-2013 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
/** @file stdc++.h
* This is an implementation file for a precompiled header.
*/
// Also writing "using namespace std;" here so that you dont need to write it everytime you start a cpp file
using namespace std;
// 17.4.1.2 Headers
// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#define lsb(x) (x & (-x))
using ull = unsigned long long;
using ll = long long;
using namespace std;
const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy[] = {-1, 0, 1, -1, 1, 0, -1, 1};
int dist(const pair<int, int> &x, const pair<int, int> &y) {
return abs(x.first - y.first) + abs(x.second - y.second);
}
int is_attacked(const pair<int, int> &x, const pair<int, int> &y) { // x - king, y - pawn
return (x.second == y.second && x.first == y.first + 1) || (y.first == 2 && x.first == 4 && x.second == y.second);
}
int king_attacked(const pair<int, int> &x, const pair<int, int> &y) {
if (x == y)
return true;
for (int k = 0; k < 8; ++k) {
if (x.first + dx[k] == y.first && x.second + dy[k] == y.second)
return true;
}
return false;
}
int ok(pair<int, int> x) {
return x.first >= 1 && x.first <= 8 && x.second >= 1 && x.second <= 8;
}
int to_num(const vector<pair<int, int>> &p, int move) {
int x = 0;
for (int i = 0; i < 3; ++i) {
x = (x * 9 + p[i].first) * 9 + p[i].second;
}
x = (x << 1) | move;
return x;
}
pair<vector<pair<int, int>>, int> from_num(int x) {
int move = x & 1;
x >>= 1;
vector<pair<int, int>> p;
while (x > 0) {
int c = x % 9;
x = (x - c) / 9;
int l = x % 9;
x = (x - c) / 9;
p.push_back({l, c});
}
reverse(p.begin(), p.end());
return make_pair(p, move);
}
map<int, int> f;
map<int, vector<int>> v, vt;
void clear_edges(int state) {
for (auto it : v[state])
vt[it].erase(find(vt[it].begin(), vt[it].end(), state));
}
void add_edge(int s1, int s2) {
v[s1].push_back(s2);
vt[s2].push_back(s1);
}
int back(const vector<pair<int, int>> &p, int move) {
int state = to_num(p, move);
if (f.count(state))
return f[state];
f[state] = -1;
if (p[1] == p[2])
return f[state] = 0;
if (move == 0 && p[1].first == 8)
return f[state] = 1;
vector<pair<int, int>> p2;
for (auto it : p)
p2.push_back(it);
if (move == 0) {
p2[1].first += 1;
if (dist(p2[1], p2[2]) > 0 && dist(p2[1], p2[0]) > 0 && ok(p2[1])) {
int ans = back(p2, 1 - move);
if (ans == 1) {
clear_edges(state);
f[state] = 1;
return 1;
}
int s2 = to_num(p2, 1 - move);
add_edge(state, s2);
}
p2[1].first -= 1;
if (p2[1].first == 2) {
p2[1].first += 2;
if (dist(p2[1], p2[2]) > 0 && dist(p2[1], p2[0]) > 0 && ok(p2[1])) {
int ans = back(p2, 1 - move);
if (ans == 1) {
clear_edges(state);
f[state] = 1;
return 1;
}
int s2 = to_num(p2, 1 - move);
add_edge(state, s2);
}
p2[1].first -= 2;
}
for (int k = 0; k < 8; ++k) {
p2[0].first += dx[k];
p2[0].second += dy[k];
if (ok(p2[0]) && !king_attacked(p2[0], p2[2]) && dist(p2[0], p2[1]) > 0) {
int ans = back(p2, 1 - move);
if (ans == 1) {
clear_edges(state);
f[state] = 1;
return 1;
}
int s2 = to_num(p2, 1 - move);
add_edge(state, s2);
}
p2[0].first -= dx[k];
p2[0].second -= dy[k];
}
} else {
int nr = 0;
for (int k = 0; k < 8; ++k) {
p2[2].first += dx[k];
p2[2].second += dy[k];
if (ok(p2[2]) && !king_attacked(p2[0], p2[2]) && !is_attacked(p2[2], p2[1])) {
nr += 1;
int ans = back(p2, 1 - move);
if (ans == 0) {
clear_edges(state);
f[state] = 0;
return 0;
}
int s2 = to_num(p2, 1 - move);
add_edge(state, s2);
}
p2[2].first -= dx[k];
p2[2].second -= dy[k];
}
if (nr == 0 && !is_attacked(p2[2], p2[1])) {
clear_edges(state);
f[state] = 0;
}
}
return f[state];
}
void bfs(queue<int> &q) {
int cnt = 0;
while (!q.empty()) {
int s = q.front();
q.pop();
int x = from_num(s).second;
for (auto it : vt[s]) {
if (f[it] != -1)
continue;
if (f[s] == x) {
f[it] = x;
q.push(it);
cnt += 1;
} else {
int all = f[s];
bool c = true;
for (auto adj : v[it])
c &= all == f[adj];
if (c && all != -1) {
f[it] = all;
cnt += 1;
q.push(it);
}
}
}
}
//cout << cnt << "\n";
}
void solve() {
string s1, s2, s3, s4;
cin >> s1 >> s2 >> s3 >> s4;
int move = 0;
if (s4 == "b")
move = 1;
int c1 = s1[0] - 'a' + 1;
int l1 = s1[1] - '0';
int c2 = s2[0] - 'a' + 1;
int l2 = s2[1] - '0';
int c3 = s3[0] - 'a' + 1;
int l3 = s3[1] - '0';
vector<pair<int,int>> p;
p.push_back({l1, c1});
p.push_back({l2, c2});
p.push_back({l3, c3});
int x = to_num(p, move);
//cout << f[x] << "\n";
if (f[x] == 0)
cout << "Draw\n";
else
cout << "Win\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
vector<int> p;
int x = 0, mx = 531441 * 2;
while (x < mx) {
x += 1;
vector<pair<int, int>> p;
int move;
tie(p, move) = from_num(x);
if (p.size() < 3)
continue;
if (p.size() > 3)
break;
bool c = true;
for (auto it : p)
c &= ok(it);
c = c && !king_attacked(p[0], p[2]) && p[0] != p[1] && p[0] != p[2] && p[1] != p[2];
if (c) {
/**for (auto it : p)
cout << it.first << " " << it.second << endl;
cout << endl;
**/
back(p, move);
}
}
queue<int> q;
for (auto it : f) {
if (it.second != -1)
q.push(it.first);
}
// cout << q.size() << endl;
bfs(q);
int t;
cin >> t;
while (t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
6 a2 d7 e7 w b6 d7 e7 b b6 d7 e7 w b5 a2 b2 w a6 a2 a4 b g6 g7 h8 b