QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#177577#7180. Forward-Capturing Pawnsucup-team859WA 1016ms119752kbC++148.8kb2023-09-13 04:35:052023-09-13 04:35:06

Judging History

你现在查看的是最新测评结果

  • [2023-09-13 04:35:06]
  • 评测
  • 测评结果:WA
  • 用时:1016ms
  • 内存:119752kb
  • [2023-09-13 04:35:05]
  • 提交

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) {
        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: 100
Accepted
time: 848ms
memory: 119584kb

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
Wrong Answer
time: 1016ms
memory: 119752kb

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:

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
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:

wrong answer 1st lines differ - expected: 'Draw', found: 'Win'