QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#177310 | #7180. Forward-Capturing Pawns | ucup-team859 | WA | 15ms | 4888kb | C++14 | 7.9kb | 2023-09-12 20:11:10 | 2023-09-12 20:11:11 |
Judging History
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;
struct board {
vector<pair<int,int>> v;
int move, cnt;
bool operator < (const board &aux) const {
for (int i = 0; i < 3; ++i) {
if (v[i] != aux.v[i])
return v[i] < aux.v[i];
}
if (move != aux.move)
return move < aux.move;
return cnt < aux.cnt;
}
};
map<board, int> f;
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 nr = 0;
vector<int> perm = {0, 1, 2, 3, 4, 5, 6, 7};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int back(const vector<pair<int, int>> &p, int move) {
int cnt = 0;
while (f.count({p, move, cnt}) && f[{p, move, cnt}] == -1)
++cnt;
if (f.count({p, move, cnt}))
return f[{p, move, cnt}];
if (p[1] == p[2] || (cnt >= 3 && move == 1))
return f[{p, move, cnt}] = 0;
if (move == 0 && p[1].first == 8)
return f[{p, move, cnt}] = 1;
f[{p, move, cnt}] = -1;
vector<pair<int, int>> p2;
for (auto it : p)
p2.push_back(it);
shuffle(perm.begin(), perm.end(), rng);
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) {
f[{p, move, cnt}] = 1;
return 1;
}
}
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) {
f[{p, move, cnt}] = 1;
return 1;
}
}
p2[1].first -= 2;
}
for (int k = 0; k < 8; ++k) {
p2[0].first += dx[perm[k]];
p2[0].second += dy[perm[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) {
f[{p, move, cnt}] = 1;
return 1;
}
}
p2[0].first -= dx[perm[k]];
p2[0].second -= dy[perm[k]];
}
if (f[{p, move, cnt}] == -1)
f[{p, move, cnt}] = 0;
} else {
int nr = 0;
for (int k = 0; k < 8; ++k) {
p2[2].first += dx[perm[k]];
p2[2].second += dy[perm[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) {
f[{p, move, cnt}] = 0;
return 0;
}
}
p2[2].first -= dx[perm[k]];
p2[2].second -= dy[perm[k]];
}
if (nr == 0 && !is_attacked(p2[2], p2[1]))
f[{p, move, cnt}] = 0;
else if (f[{p, move, cnt}] == -1)
f[{p, move, cnt}] = 1;
}
return f[{p, move, cnt}];
}
void solve() {
string s1, s2, s3, s4;
cin >> s1 >> s2 >> s3 >> s4;
int move = 0;
if (s4 == "b")
move = 1;
static int cnt = 0;
//cnt += 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';
// int l1, c1, l2, c2, l3, c3;
// l1 = rand() % 8 + 1;
// l2 = rand() % 8 + 1;
// l3 = rand() % 8 + 1;
// c1 = rand() % 8 + 1;
// c2 = rand() % 8 + 1;
// c3 = rand() % 8 + 1;
vector<pair<int,int>> p;
p.push_back({l1, c1});
p.push_back({l2, c2});
p.push_back({l3, c3});
int ans = back(p, move);
if (ans == 0)
cout << "Draw\n";
else
cout << "Win\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 100000;
cin >> t;
while (t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 15ms
memory: 4888kb
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
output:
Win Draw Win Win Win Draw
result:
wrong answer 1st lines differ - expected: 'Draw', found: 'Win'