QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#177310#7180. Forward-Capturing Pawnsucup-team859WA 15ms4888kbC++147.9kb2023-09-12 20:11:102023-09-12 20:11:11

Judging History

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

  • [2023-09-12 20:11:11]
  • 评测
  • 测评结果:WA
  • 用时:15ms
  • 内存:4888kb
  • [2023-09-12 20:11:10]
  • 提交

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;

vector<int> perm = {0, 1, 2, 3, 4, 5, 6, 7};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int back(const vector<pair<int, int>> &p, int move) {
    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 >= 3 && move == 1))
        return f[{p, move, cnt}] = 0;

    if (move == 0 && p[1].first == 8)
        return f[{p, move, cnt}] = 1;

    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 (int k = 0; k < 8; ++k) {
            p2[0].first += dx[perm[k]];
            p2[0].second += dy[perm[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[perm[k]];
            p2[0].second -= dy[perm[k]];
        }

        if (f[{p, move, cnt}] == -1)
            f[{p, move, cnt}] = 0;
    } else {
        int nr = 0;
        for (int k = 0; k < 8; ++k) {
            p2[2].first += dx[perm[k]];
            p2[2].second += dy[perm[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[perm[k]];
            p2[2].second -= dy[perm[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;

    static int cnt = 0;
    //cnt += 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';
    // int l1, c1, l2, c2, l3, c3;
    // l1 = rand() % 8 + 1;
    // l2 = rand() % 8 + 1;
    // l3 = rand() % 8 + 1;

    // c1 = rand() % 8 + 1;
    // c2 = rand() % 8 + 1;
    // c3 = rand() % 8 + 1;

    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 = 100000;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 15ms
memory: 4888kb

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:

Win
Draw
Win
Win
Win
Draw

result:

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