QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#177322#7180. Forward-Capturing Pawnsucup-team859TL 224ms15120kbC++147.6kb2023-09-12 20:38:472023-09-12 20:38:48

Judging History

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

  • [2023-09-12 20:38:48]
  • 评测
  • 测评结果:TL
  • 用时:224ms
  • 内存:15120kb
  • [2023-09-12 20:38:47]
  • 提交

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;

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

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

    for (auto i : p) {
	int nr = 0;
    	for (auto j : p) {
		if (dist(i, j) == 0)
			++nr;
	}
	if (nr != 1)
		cout << "MLP\n";
    }

    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 (auto k : perm) {
            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) {
                    f[{p, move, cnt}] = 1;
                    return 1;
                }
            }
            p2[0].first -= dx[k];
            p2[0].second -= dy[k];
        }

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

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 224ms
memory: 15120kb

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
Time Limit Exceeded

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: