QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#177581 | #7180. Forward-Capturing Pawns | ucup-team859 | AC ✓ | 987ms | 119536kb | C++14 | 9.3kb | 2023-09-13 04:43:35 | 2023-09-13 04:43:35 |
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;
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);
}
const int NMAX = 1100000;
unordered_map<int, int> f;
vector<int> v[NMAX], vt[NMAX];
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 = p;
if (move == 0) {
int nr = 0;
p2[1].first += 1;
if (dist(p2[1], p2[2]) > 0 && dist(p2[1], p2[0]) > 0 && ok(p2[1])) {
nr += 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])) {
nr += 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);
nr += 1;
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];
}
if (nr == 0)
f[state] = 0;
} 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 cnt = 0;
for (auto it : f) {
if (it.second == -1) {
cnt += 1;
vector<pair<int, int>> p;
int move;
tie(p, move) = from_num(it.first);
cout << move << endl;
for (auto it : p)
cout << it.first << " " << it.second << endl;
for (auto adj : v[it.first])
cout << f[adj] << " ";
cout << endl;
break;
}
}
cout << cnt << endl;
**/
int t;
cin >> t;
while (t--)
solve();
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 844ms
memory: 119536kb
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: 0
Accepted
time: 987ms
memory: 119536kb
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...
result:
ok 332912 lines
Extra Test:
score: 0
Extra Test Passed