QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#177322 | #7180. Forward-Capturing Pawns | ucup-team859 | TL | 224ms | 15120kb | C++14 | 7.6kb | 2023-09-12 20:38:47 | 2023-09-12 20:38:48 |
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;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int back(const vector<pair<int, int>> &p, int move) {
vector<int> perm = {0, 1, 2, 3, 4, 5, 6, 7};
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 >= 5)
return f[{p, move, cnt}] = 0;
if (move == 0 && p[1].first == 8)
return f[{p, move, cnt}] = 1;
for (auto i : p) {
int nr = 0;
for (auto j : p) {
if (dist(i, j) == 0)
++nr;
}
if (nr != 1)
cout << "MLP\n";
}
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 (auto k : perm) {
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) {
f[{p, move, cnt}] = 1;
return 1;
}
}
p2[0].first -= dx[k];
p2[0].second -= dy[k];
}
if (f[{p, move, cnt}] == -1)
f[{p, move, cnt}] = 0;
} else {
int nr = 0;
for (auto k : perm) {
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) {
f[{p, move, cnt}] = 0;
return 0;
}
}
p2[2].first -= dx[k];
p2[2].second -= dy[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;
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 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;
cin >> t;
while (t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 224ms
memory: 15120kb
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:
Draw Draw Win Win Draw Draw
result:
ok 6 lines
Test #2:
score: -100
Time Limit Exceeded
input:
332912 h8 h7 f8 b h8 h7 f8 w h8 h7 e8 b h8 h7 e8 w h8 h7 d8 b h8 h7 d8 w h8 h7 c8 b h8 h7 c8 w h8 h7 b8 b h8 h7 b8 w h8 h7 a8 b h8 h7 a8 w h8 h7 f7 b h8 h7 f7 w h8 h7 e7 b h8 h7 e7 w h8 h7 d7 b h8 h7 d7 w h8 h7 c7 b h8 h7 c7 w h8 h7 b7 b h8 h7 b7 w h8 h7 a7 b h8 h7 a7 w h8 h7 h6 b h8 h7 h6 w h8 h7 g...
output:
Draw Draw Draw Win Win Win Win Win Win Win Win Win Draw Draw Draw Win Win Win Win Win Win Win Win Win Win Win Draw Win Draw Win Draw Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win...