QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #548839 | #2821. 鸭棋 | Flying_hq | WA | 2ms | 3840kb | C++14 | 16.6kb | 2024-09-05 21:26:00 | 2024-09-05 21:26:00 |
Judging History
answer
// Problem: P5380 [THUPC2019] 鸭棋
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5380
// Memory Limit: 500 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
#define int long long
#define rg register
#define il inline
#define pii pair<int, int>
#define TT(T, Args) template<typename T, typename... Args>
#define up(i, a, b) for (rg int i = (a); i <= (b); i++)
#define down(i, a, b) for (rg int i = (a); i >= (b); i--)
#define rep(i, a) for (rg auto i : a)
using namespace std;
namespace xmpl_{
#define SIZE (1 << 24)
namespace Fast_read{
char buf[SIZE], *S, *T;
il char Getchar(){
if (S == T){
T = (S = buf) + fread(buf, 1, SIZE, stdin);
if (S == T) return '\n';
}
return *S++;
}
}
namespace Fast_write{
char buf[SIZE], *S = buf, *T = buf + SIZE;
il void flush(){
fwrite(buf, 1, S - buf, stdout);
S = buf;
}
il void Putchar(char c){
*S++ = c;
if (S == T) flush();
}
struct F{
~F(){
flush();
}
}fly;
#undef SIZE
}
#define gc Fast_read::Getchar
#define pc Fast_write::Putchar
il int fast_rd(){
int f = 1, x = 0;
char ch = gc();
while(ch < '0' || ch > '9'){
if (ch == '-') f = -1;
ch = gc();
}
while(ch >= '0' && ch <= '9'){
x = x * 10 + ch - '0';
ch = gc();
}
return x * f;
}
il void fast_wt(int x){
if (x < 0){
pc('-');
x = -x;
}
if (x > 9) fast_wt(x / 10);
pc(x % 10 + 48);
}
il string fast_rds(){
string s = "";
char ch = gc();
while((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9')){
s += ch;
ch = gc();
}
return s;
}
il void fast_wts(string s){
for (int i = 0; i < s.size(); i++) pc(s[i]);
}
il int rd(){
int f = 1, x = 0;
char ch = getchar();
while(ch < '0' || ch > '9'){
if (ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
TT(T, Args) il void rd(T &x){
int f = 1;
x = 0;
char ch = getchar();
while(ch < '0' || ch > '9'){
if (ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = x * 10 + ch - '0';
ch = getchar();
}
x *= f;
}
TT(T, Args) il void rd(T &x, Args &...args){
rd(x), rd(args...);
}
TT(T, Args) il void fast_rd(T &x){
int f = 1;
x = 0;
char ch = gc();
while(ch < '0' || ch > '9'){
if (ch == '-') f = -1;
ch = gc();
}
while(ch >= '0' && ch <= '9'){
x = x * 10 + ch - '0';
ch = gc();
}
x *= f;
}
TT(T, Args) il void fast_rd(T &x, Args &...args){
fast_rd(x), fast_rd(args...);
}
il void wt(int x){
if (x < 0){
putchar('-');
x = -x;
}
if (x > 9) wt(x / 10);
putchar(x % 10 + 48);
}
il string rds(){
string s = "";
char ch = getchar();
while((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9')){
s += ch;
ch = getchar();
}
return s;
}
il void wts(string s){
for (int i = 0; i < s.size(); i++) putchar(s[i]);
}
il int max(int x, int y){
return (x > y ? x : y);
}
il int min(int a, int b){
return (a < b ? a : b);
}
il int max(int x, int y, int z){
return max(x, max(y, z));
}
il int min(int a, int b, int c){
return min(a, min(b, c));
}
il int qmul(int a, int b, int p){
int res = 0;
while(b){
if (b & 1) res = (res + a) % p;
a = (a + a) % p;
b >>= 1ll;
}
return res;
}
il int qpow(int a, int b, int p){
int res = 1;
while(b){
if (b & 1) res = qmul(res, a, p);
a = qmul(a, a, p);
b >>= 1ll;
}
return res;
}
const int Q = 1e6 + 5;
int fac[Q] = {0}, inv[Q] = {0}, finv[Q] = {0};
il void init(int n, int p){
fac[0] = inv[0] = finv[0] = fac[1] = inv[1] = finv[1] = 1;
for (int i = 2; i <= n; i++){
fac[i] = 1ll * fac[i - 1] * i % p;
inv[i] = (p - 1ll * p / i * inv[p % i] % p) % p;
finv[i] = 1ll * finv[i - 1] * inv[i] % p;
}
}
il int A(int n, int m, int p){
if (m > n || m < 0) return 0;
return 1ll * fac[n] * finv[n - m] % p;
}
il int C(int n, int m, int p){
if (m > n || m < 0) return 0;
return 1ll * fac[n] * finv[m] % p * finv[n - m] % p;
}
il int Lucas(int n, int m, int p){
if (!m) return 1;
return (1ll * C(n % p, m % p, p) * Lucas(n / p, m / p, p)) % p;
}
il int gcd(int a, int b){
if (!b) return a;
return gcd(b, a % b);
}
il int lcm(int a, int b){
return 1ll * a * b / gcd(a, b);
}
const int W = 1e5 + 5;
struct int64{
int d[W];
int64(){
memset(d, 0, sizeof(d));
d[0] = 1;
}
int64(int x){
int64();
int it = 0;
while(x){
d[++it] = x % 10;
x /= 10;
}
d[0] = it;
}
bool operator < (const int64 &x) const{
if (d[0] ^ x.d[0]) return d[0] < x.d[0];
int it = d[0];
while(d[it] == x.d[it] && it > 1) it--;
if (it >= 1) return d[it] < x.d[it];
else return 0;
}
int64 operator * (const int &x){
int64 ans;
int len;
ans.d[0] = d[0];
for (int i = 1; i <= d[0]; i++) ans.d[i] = d[i] * x;
for (int i = 1; i <= ans.d[0] || ans.d[i]; i++){
ans.d[i + 1] += ans.d[i] / 10;
ans.d[i] %= 10;
len = i + 1;
}
ans.d[0] = len;
if (!ans.d[len]) ans.d[0]--;
return ans;
}
int64 operator / (const int &x){
int64 ans;
ans.d[0] = d[0];
int res = 0;
for (int i = d[0]; i >= 1; i--){
res = res * 10 + d[i];
ans.d[i] = res / x;
res %= x;
}
while(!ans.d[ans.d[0]] && ans.d[0] > 1) ans.d[0]--;
return ans;
}
};
std::ostream &operator << (std::ostream &ans, const int64 &x){
for (int i = x.d[0]; i >= 1; i--) ans << x.d[i];
return ans;
}
const int p = 998244353;
struct Mint{
int x;
Mint(){};
Mint(int x) : x(x){}
friend std::istream &operator >> (std::istream &in, Mint &a){
return in >> a.x;
}
friend std::ostream &operator << (std::ostream &out, Mint a){
return out << a.x;
}
friend Mint operator + (Mint a, Mint b){
return (a.x + b.x + p) % p;
}
friend Mint operator - (Mint a, Mint b){
return (a.x - b.x + p) % p;
}
friend Mint operator * (Mint a, Mint b){
return 1ll * a.x * b.x % p;
}
friend Mint operator / (Mint a, Mint b){
return (a.x / b.x + p) % p;
}
friend Mint &operator += (Mint &a, Mint b){
return a = a + b;
}
friend Mint &operator -= (Mint &a, Mint b){
return a = a - b;
}
friend Mint &operator *= (Mint &a, Mint b){
return a = a * b;
}
friend Mint &operator /= (Mint &a, Mint b){
return a = a / b;
}
friend Mint &operator ++ (Mint &a){
return a += 1;
}
friend Mint &operator -- (Mint &a){
return a -= 1;
}
friend bool operator == (Mint a, Mint b){
return a.x == b.x;
}
friend bool operator <= (Mint a, Mint b){
return a.x <= b.x;
}
friend bool operator >= (Mint a, Mint b){
return a.x >= b.x;
}
friend bool operator < (Mint a, Mint b){
return a.x < b.x;
}
friend bool operator > (Mint a, Mint b){
return a.x > b.x;
}
friend bool operator != (Mint a, Mint b){
return !(a == b);
}
friend Mint operator ^ (Mint a, int b){
Mint ans = 1;
for (; b; b >>= 1, a *= a) if (b & 1) ans *= a;
return ans;
}
};
}
using namespace xmpl_;
using namespace std;
const int N = 2e5 + 5, M = 1e6 + 5, K = 2e6 + 5;
int a[11][10] = {
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 11, 12, 13, 14, 15, 14, 13, 12, 11},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 16, 0, 0, 0, 0, 0, 0, 0, 16},
{0, 17, 0, 17, 0, 17, 0, 17, 0, 17},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 7, 0, 7, 0, 7, 0, 7, 0, 7},
{0, 6, 0, 0, 0, 0, 0, 0, 0, 6},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 2, 3, 4, 5, 4, 3, 2, 1},
};
bool turn = 1;//turn = 1 表示红方走棋，0 表示蓝方
bool truemove = true;//判断移动是否合法
string error = "Invalid command";
string movechess = "NA";
string leavegamechess = "NA";//吃棋
string jiangjun = "no";//将军
string gameover = "no";//结束
string bluechess[] = {"NA", "blue car", "blue horse", "blue elephant", "blue guard", "blue captain", "blue duck", "blue soldier"};
string redchess[] = {"NA", "red car", "red horse", "red elephant", "red guard", "red captain", "red duck", "red soldier"};
map<int, string> mp;
/*
red:
车 1
马 2
象 3
士 4
王 5
鸭 6
兵 7
blue:(+10)
车 11
马 12
象 13
士 14
王 15
鸭 16
兵 17
*/
il void print(){
up(i, 1, 10){
up(j, 1, 9){
cout << a[i][j] << " ";
}
cout << endl;
}
}
il void init(){
mp[1] = "red car";
mp[2] = "red horse";
mp[3] = "red elephant";
mp[4] = "red guard";
mp[5] = "red captain";
mp[6] = "red duck";
mp[7] = "red soldier";
mp[11] = "blue car";
mp[12] = "blue horse";
mp[13] = "blue elephant";
mp[14] = "blue guard";
mp[15] = "blue captain";
mp[16] = "blue duck";
mp[17] = "blue soldier";
}
il void clear(){
}
/*
red:
车 1
马 2
象 3
士 4
王 5
鸭 6
兵 7
blue:(+10)
车 11
马 12
象 13
士 14
王 15
鸭 16
兵 17
*/
il void move(int x, int y, int edx, int edy){
int type = a[x][y];
if (type == 0) return truemove = false, void();
if (type > 10 && turn) return truemove = false, void();
if (type > 0 && type < 10 && !turn) return truemove = false, void();
if (type > 10) type -= 10;
movechess = mp[a[x][y]];
if (a[x][y] <= 10 && a[edx][edy] <= 10 && a[x][y] && a[edx][edy]) return truemove = false, void();
if (a[x][y] >= 10 && a[edx][edy] >= 10 && a[x][y] && a[edx][edy]) return truemove = false, void();
if (type == 1){
if (x != edx && y != edy) return truemove = false, void();
if (x == edx){
if (y > edy) swap(y, edy);
up(i, y + 1, edy - 1) if (a[x][i]) return truemove = false, void();
}
else{
if (x > edx) swap(x, edx);
up(i, x + 1, edx - 1) if (a[i][x]) return truemove = false, void();
}
if (a[edx][edy]){
leavegamechess = mp[a[edx][edy]];
a[edx][edy] = a[x][y], a[x][y] = 0;
return ;
}
else{
a[edx][edy] = a[x][y], a[x][y] = 0;
return ;
}
return truemove = false, void();
}
else if (type == 2){
for (int sx = -1; sx <= 1; sx += 2){
for (int sy = -1; sy <= 1; sy += 2){
if (!a[x + sx][y] && x + sx * 2 == edx && y + sy == edy){
if (a[edx][edy]){
leavegamechess = mp[a[edx][edy]];
a[edx][edy] = a[x][y], a[x][y] = 0;
}
else{
a[edx][edy] = a[x][y], a[x][y] = 0;
}
return ;
}
if (!a[x][y + sy] && x + sx == edx && y + sy * 2 == edy){
if (a[edx][edy]){
leavegamechess = mp[a[edx][edy]];
a[edx][edy] = a[x][y], a[x][y] = 0;
}
else{
a[edx][edy] = a[x][y], a[x][y] = 0;
}
return ;
}
}
}
return truemove = false, void();
}
else if (type == 3){
for (int sx = -1; sx <= 1; sx += 2){
for (int sy = -1; sy <= 1; sy += 2){
if (!a[x + sx][y + sy] && x + sx * 2 == edx && y + sy * 2 == edy){
if (a[edx][edy]){
leavegamechess = mp[a[edx][edy]];
a[edx][edy] = a[x][y], a[x][y] = 0;
}
else{
a[edx][edy] = a[x][y], a[x][y] = 0;
}
return ;
}
}
}
return truemove = false, void();
}
else if (type == 4){
for (int sx = -1; sx <= 1; sx += 2){
for (int sy = -1; sy <= 1; sy += 2){
if (x + sx == edx && y + sy == edy){
if (a[edx][edy]){
leavegamechess = mp[a[edx][edy]];
a[edx][edy] = a[x][y], a[x][y] = 0;
}
else{
a[edx][edy] = a[x][y], a[x][y] = 0;
}
return ;
}
}
}
return truemove = false, void();
}
else if (type == 5){
for (int sx = -1; sx <= 1; sx += 2){
for (int sy = -1; sy <= 1; sy += 2){
if ((x + sx == edx && y == edy) || (x == edx && y + sy == edy)){
if (a[edx][edy]){
leavegamechess = mp[a[edx][edy]];
a[edx][edy] = a[x][y], a[x][y] = 0;
}
else{
a[edx][edy] = a[x][y], a[x][y] = 0;
}
return ;
}
}
}
return truemove = false, void();
}
else if (type == 6){
for (int sx = -1; sx <= 1; sx += 2){
for (int sy = -1; sy <= 1; sy += 2){
if (!a[x + sx * 2][y + sy] && !a[x + sx][y] && x + sx * 3 == edx && y + sy * 2 == edy){
if (a[edx][edy]){
leavegamechess = mp[a[edx][edy]];
a[edx][edy] = a[x][y], a[x][y] = 0;
}
else{
a[edx][edy] = a[x][y], a[x][y] = 0;
}
return ;
}
if (!a[x + sx][y + sy * 2] && !a[x][y + sy] && x + sx * 2 == edx && y + sy * 3 == edy){
if (a[edx][edy]){
leavegamechess = mp[a[edx][edy]];
a[edx][edy] = a[x][y], a[x][y] = 0;
}
else{
a[edx][edy] = a[x][y], a[x][y] = 0;
}
return ;
}
}
}
return truemove = false, void();
}
else if (type == 7){
for (int sx = -1; sx <= 1; sx++){
for (int sy = -1; sy <= 1; sy++){
if (x + sx == edx && y + sy == edy){
if (a[edx][edy]){
leavegamechess = mp[a[edx][edy]];
a[edx][edy] = a[x][y], a[x][y] = 0;
}
else{
a[edx][edy] = a[x][y], a[x][y] = 0;
}
return ;
}
}
}
return truemove = false, void();
}
}
il bool atack(int x, int y, int edx, int edy, int type){
if (type > 10) type -= 10;
if (type == 1){
if (x != edx && y != edy) return 0;
if (x == edx){
if (y > edy) swap(y, edy);
up(i, y + 1, edy - 1) if (a[x][i]) return 0;
}
else{
if (x > edx) swap(x, edx);
up(i, x + 1, edx - 1) if (a[i][y]) return 0;
}
return 1;
}
else if (type == 2){
for (int sx = -1; sx <= 1; sx += 2){
for (int sy = -1; sy <= 1; sy += 2){
if (!a[x + sx][y] && x + sx * 2 == edx && y + sy == edy) return 1;
if (!a[x][y + sy] && x + sx == edx && y + sy * 2 == edy) return 1;
}
}
return 0;
}
else if (type == 3){
for (int sx = -1; sx <= 1; sx += 2){
for (int sy = -1; sy <= 1; sy += 2){
if (!a[x + sx][y + sy] && x + sx * 2 == edx && y + sy * 2 == edy) return 1;
}
}
return 0;
}
else if (type == 4){
for (int sx = -1; sx <= 1; sx += 2){
for (int sy = -1; sy <= 1; sy += 2){
if (x + sx == edx && y + sy == edy) return 1;
}
}
return 0;
}
else if (type == 5){
for (int sx = -1; sx <= 1; sx += 2){
for (int sy = -1; sy <= 1; sy += 2){
if ((x + sx == edx && y == edy) || (x == edx && y + sy == edy)) return 1;
}
}
return 0;
}
else if (type == 6){
for (int sx = -1; sx <= 1; sx += 2){
for (int sy = -1; sy <= 1; sy += 2){
if (!a[x + sx * 2][y + sy] && !a[x + sx][y] && x + sx * 3 == edx && y + sy * 2 == edy) return 1;
if (!a[x + sx][y + sy * 2] && !a[x][y + sy] && x + sx * 2 == edx && y + sy * 3 == edy) return 1;
}
}
return 0;
}
else if (type == 7){
for (int sx = -1; sx <= 1; sx++){
for (int sy = -1; sy <= 1; sy++){
if (x + sx == edx && y + sy == edy) return 1;
}
}
return 0;
}
}
il bool checkmate(int x, int y){
if (!a[x][y]) return 0;
if (a[x][y] <= 10){
//(x,y) 红棋
int posx = 0, posy = 0;
up(i, 1, 10){
up(j, 1, 9){
if (a[i][j] == 15){
posx = i, posy = j;
break;
}
}
if (posx && posy) break;
}
if (atack(x, y, posx, posy, a[x][y])) return 1;
}
else{
//(x,y) 蓝棋
int posx = 0, posy = 0;
up(i, 1, 10){
up(j, 1, 9){
if (a[i][j] == 5){
posx = i, posy = j;
break;
}
}
if (posx && posy) break;
}
if (atack(x, y, posx, posy, a[x][y])) return 1;
}
return 0;
}
il void checkjj(){
up(i, 1, 10){
up(j, 1, 9){
if (checkmate(i, j)){
jiangjun = "yes";
return ;
}
}
}
jiangjun = "no";
}
il void print_ans(){
cout << movechess << ";" << leavegamechess << ";" << jiangjun << ";" << gameover << endl;
}
int q, sx, sy, ex, ey;
il void work(){
q = rd();
while(q--){
movechess = leavegamechess = "NA", jiangjun = "no";
truemove = true;
rd(sx, sy, ex, ey);
sx++, sy++, ex++, ey++;
sx = 10 - sx + 1, ex = 10 - ex + 1;
//如果游戏已结束
if (gameover == "yes"){
cout << error << endl;
continue;
}
// cout << sx << " " << sy << " " << ex << " " << ey << " " << a[sx][sy] << endl;
move(sx, sy, ex, ey);//棋子移动
// print();
if (!truemove){
cout << error << endl;
continue;
}
checkjj();//检查是否形成将军局面
if (leavegamechess == "blue captain" || leavegamechess == "red captain"){
gameover = "yes";
jiangjun = "no";
}
print_ans();//输出答案
turn = (!turn);//转换行动方
}
}
signed main(){
// #define file 114514
#ifdef file
freopen("code.in", "r", stdin);
freopen("code.out", "w", stdout);
#endif
init();
int t = 1;
// t = rd();
while(t--){
// clear();
work();
// puts("");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3840kb
input:
18 0 0 7 0 9 0 8 0 0 1 1 3 0 2 2 0 0 3 1 2 0 4 0 3 9 4 8 4 3 2 2 3 7 0 4 2 7 0 5 3 9 2 7 4 2 0 4 3 9 1 8 3 4 3 6 6 7 4 9 2 8 4 9 4 6 6 9 4 9 8 8 8
output:
Invalid command Invalid command Invalid command Invalid command red guard;NA;no;no Invalid command blue captain;NA;no;no red soldier;NA;no;no Invalid command Invalid command blue elephant;NA;no;no red duck;NA;no;no blue horse;NA;no;no red duck;blue soldier;no;no Invalid command blue captain;NA;yes;n...
result:
ok 18 lines
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 3600kb
input:
1000 0 7 2 6 3 8 4 8 3 0 4 0 0 6 8 6 0 3 1 4 6 2 5 3 6 0 5 0 0 4 1 4 9 7 7 6 9 5 8 4 9 5 8 6 7 0 3 2 3 0 2 1 9 2 7 4 5 3 4 2 1 4 2 4 0 1 2 2 6 0 7 1 9 5 8 4 2 6 1 4 2 1 1 2 2 8 8 1 9 8 8 8 6 6 7 7 7 4 9 2 8 8 8 0 2 0 5 2 2 8 6 1 1 7 1 1 0 3 1 2 3 8 3 7 9 0 8 0 0 3 1 2 3 4 2 5 9 6 9 4 6 4 5 5 4 2 7 4...
output:
red horse;NA;no;no Invalid command Invalid command Invalid command Invalid command blue soldier;NA;no;no Invalid command red captain;NA;no;no blue horse;NA;no;no Invalid command Invalid command Invalid command red soldier;NA;no;no blue elephant;NA;no;no Invalid command red captain;NA;no;no Invalid c...
result:
wrong answer 50th lines differ - expected: 'blue car;NA;no;no', found: 'blue car;blue car;no;no'