QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#177581#7180. Forward-Capturing Pawnsucup-team859AC ✓987ms119536kbC++149.3kb2023-09-13 04:43:352023-09-13 04:43:35

Judging History

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

  • [2023-09-13 04:43:35]
  • 评测
  • 测评结果:AC
  • 用时:987ms
  • 内存:119536kb
  • [2023-09-13 04:43:35]
  • 提交

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,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

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