QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#177572#7180. Forward-Capturing Pawnsucup-team859TL 0ms0kbC++148.8kb2023-09-13 04:31:332023-09-13 04:31:34

Judging History

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

  • [2023-09-13 04:31:34]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-09-13 04:31:33]
  • 提交

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

output:


result: