QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #138145 | #6341. The Last Battle | jajco | 0 | 0ms | 0kb | C++17 | 7.2kb | 2023-08-11 01:16:12 | 2023-08-11 01:16:13 |
Anna
#pragma GCC optimize("O3")
#include <vector>
#include <cassert>
#include <string>
#define REP(i, n) for (int i=0; i<(n); ++i)
#define sz(A) (int(A.size()))
#define V std::vector
typedef long long ll;
typedef V <int> vi;
typedef V <ll> vll;
typedef V <bool> vb;
struct pkt{
int x,y;
};
void Agenz(vi &sid, V <vi> &odl, V <pkt> &spoz, V <V <pkt>> &sejfy){
static bool czy=0;
if (czy)
return;
czy=1;
int sbit=8;
odl.resize(1<<sbit, vi(1<<sbit, 1e9));
{
int fm=1<<sbit;
for (int i=0; i<fm; ++i){
odl[i][i]=0;
for (int j=1; j<fm; j<<=1){
int ni=i^j;
odl[i][ni]=1;
for (int j2=j<<1; j2<fm; j2<<=1)
odl[i][ni^j2]=1;
}
}
for (int k=0; k<fm; ++k)
for (int i=0; i<fm; ++i)
for (int j=0; j<fm; ++j)
odl[i][j]=std::min(odl[i][j],
odl[i][k]+odl[k][j]);
//sid={0, 31, 227};/*
for (int k=0; k<fm; ++k)
for (int i=0; i<fm; ++i){
if (odl[k][i]<=2)
continue;
for (int j=0; j<fm; ++j){
if (odl[k][j]<=2||odl[i][j]<=2)
continue;
sid={k, i, j};
printf("%d %d %d\n", k, i, j);
goto brk1;
}
}
brk1:
;
}
spoz={{6, 0}, {7, 1}};
{
pkt xd={0, 2};
while (xd.y<8){
spoz.push_back(xd);
++xd.x,++xd.y;
}
}
sejfy.resize(3, V <pkt>());
{
auto prostokat=[&](int xp, int xk, int yp, int yk){
std::vector <pkt> r;
for (int x=xp; x<=xk; ++x)
for (int y=yp; y<=yk; ++y)
r.push_back({x, y});
return r;
};
sejfy[0]=prostokat(0, 2, 6, 7);
sejfy[1]=prostokat(5, 7, 4, 5);
sejfy[2]=prostokat(3, 4, 0, 2);
}
}
#include "Anna.h"
void Anna(int X, int Y, int N, std::string S){
while (S.size()<49)
S+='A';
auto czypokr=[&](const V <pkt> &v, int x, int y){
for (const auto &i : v)
if (i.x==x||i.y==y)
return 1;
return 0;
};
auto enc=[&](int i, int len){
vb r;
for (int j=1; j<(1<<len); j<<=1)
r.push_back(bool(i&j));
return r;
};
auto dec=[&](const vb &i){
int r=0;
for (int j=1,p=0; p<sz(i); j<<=1,++p)
if (i[p])
r+=j;
return r;
};
V <vb> czy(8, vb(8, 0));
for (int i=0; i<8; ++i)
czy[X][i]=czy[i][Y]=1;
static vi sid; static V <vi> odl; static V <pkt> spoz;
static V <V <pkt>> sejfy;
Agenz(sid, odl, spoz, sejfy);
int snum=-1;
for (int i=0; i<3; ++i)
if (!czypokr(sejfy[i], X, Y)){
snum=i;
break;
}
{ // redundantne na snum enc.
vb buf=enc(sid[snum], 8);
int cnt=0;
for (const auto &i : spoz)
if (!czy[i.x][i.y])
Paint(i.x, i.y, buf[cnt++]),czy[i.x][i.y]=1;
}
{ // sejf
vb buf=enc(X+8*Y, 6);
int cnt=0;
for (const auto &i : sejfy[snum]){
assert(!czy[i.x][i.y]);
Paint(i.x, i.y, buf[cnt++]),czy[i.x][i.y]=1;
}
}
{ // reszta czyli S
int cnt=0;
for (int x=0; x<8; ++x)
for (int y=0; y<8; ++y)
if (!czy[x][y])
Paint(x, y, S[cnt++]-'A');
}
printf("A: x=%d y=%d snum=%d S=%s\n", X, Y, snum, S.data());
}
Bruno
#include <vector>
#include <cassert>
#include <string>
#define REP(i, n) for (int i=0; i<(n); ++i)
#define sz(A) (int(A.size()))
#define V std::vector
typedef long long ll;
typedef V <int> vi;
typedef V <ll> vll;
typedef V <bool> vb;
struct pkt{
int x,y;
};
void Bgenz(vi &sid, V <vi> &odl, V <pkt> &spoz, V <V <pkt>> &sejfy){
static bool czy=0;
if (czy)
return;
czy=1;
int sbit=8;
odl.resize(1<<sbit, vi(1<<sbit, 1e9));
{
int fm=1<<sbit;
for (int i=0; i<fm; ++i){
odl[i][i]=0;
for (int j=1; j<fm; j<<=1){
int ni=i^j;
odl[i][ni]=1;
for (int j2=j<<1; j2<fm; j2<<=1)
odl[i][ni^j2]=1;
}
}
for (int k=0; k<fm; ++k)
for (int i=0; i<fm; ++i)
for (int j=0; j<fm; ++j)
odl[i][j]=std::min(odl[i][j],
odl[i][k]+odl[k][j]);
//sid={0, 31, 227};/*
for (int k=0; k<fm; ++k)
for (int i=0; i<fm; ++i){
if (odl[k][i]<=2)
continue;
for (int j=0; j<fm; ++j){
if (odl[k][j]<=2||odl[i][j]<=2)
continue;
sid={k, i, j};
goto brk1;
}
}
brk1:
;
}
spoz={{6, 0}, {7, 1}};
{
pkt xd={0, 2};
while (xd.y<8){
spoz.push_back(xd);
++xd.x,++xd.y;
}
}
sejfy.resize(3, V <pkt>());
{
auto prostokat=[&](int xp, int xk, int yp, int yk){
std::vector <pkt> r;
for (int x=xp; x<=xk; ++x)
for (int y=yp; y<=yk; ++y)
r.push_back({x, y});
return r;
};
sejfy[0]=prostokat(0, 2, 6, 7);
sejfy[1]=prostokat(5, 7, 4, 5);
sejfy[2]=prostokat(3, 4, 0, 2);
}
}
#include "Bruno.h"
std::string Bruno(int N, std::vector <std::vector <int>> T){
auto czypokr=[&](const V <pkt> &v, int x, int y){
for (const auto &i : v)
if (i.x==x||i.y==y)
return 1;
return 0;
};
auto enc=[&](int i, int len){
vb r;
for (int j=1; j<(1<<len); j<<=1)
r.push_back(bool(i&j));
return r;
};
auto dec=[&](const vb &i){
int r=0;
for (int j=1,p=0; p<sz(i); j<<=1,++p)
if (i[p])
r+=j;
return r;
};
V <vb> czy(8, vb(8, 0));
static vi sid; static V <vi> odl; static V <pkt> spoz;
static V <V <pkt>> sejfy;
Bgenz(sid, odl, spoz, sejfy);
int snum=-1;
{ // redundantne na snum enc.
vb buf;
for (const auto &i : spoz){
assert(!czy[i.x][i.y]);
buf.push_back(T[i.x][i.y]);
czy[i.x][i.y]=1;
}
int tmp=dec(buf);
int cnt=0;
for (int i : sid){
if (odl[tmp][i]<2){
assert(snum<0);
snum=cnt;
}
++cnt;
}
assert(snum>=0);
}
int X,Y;
{ // sejf
vb buf;
int cnt=0;
for (const auto &i : sejfy[snum]){
assert(!czy[i.x][i.y]);
buf.push_back(T[i.x][i.y]);
czy[i.x][i.y]=1;
}
int tmp=dec(buf);
X=tmp%8,Y=tmp/8;
}
for (int i=0; i<8; ++i)
czy[X][i]=czy[i][Y]=1;
// reszta czyli S
std::string S;
for (int x=0; x<8; ++x)
for (int y=0; y<8; ++y)
if (!czy[x][y]&&int(S.size())<N)
S+=T[x][y] ? 'B' : 'A';
printf("B: x=%d y=%d snum=%d S=%s\n\n", X, Y, snum, S.data());
return S;
}
詳細信息
Test #1:
score: 0
Wrong Answer on the first run
Manager to Anna
20000 1 7 1 A 2 3 1 A 0 1 1 A 1 1 1 A 7 4 1 A 2 3 1 A 0 3 1 B 0 7 1 A 4 2 1 B 5 4 1 A 6 0 1 B 7 3 1 A 0 7 1 A 2 3 1 A 1 6 1 A 5 2 1 B 2 7 1 B 6 3 1 A 3 3 1 A 1 7 1 A 2 3 1 A 1 2 1 A 5 3 1 A 3 5 1 A 4 3 1 A 2 3 1 A 4 6 1 B 7 3 1 B 2 3 1 A 4 4 1 A 7 3 1 A 4 5 1 B 0 7 1 A 0 3 1 B 2 0 1 B 4 1 1 A 6 0 1 ...
Anna to Manager
0 31 227 A: x=1 y=7 snum=1 S=AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA 0010000000010000000100000000000010010000100100110 A: x=2 y=3 snum=1 S=AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA 0010000000000000001000000010000010010001000101000 A: x=0 y=1 snum=1 S=AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
Manager to Bruno
Bruno to Manager
result:
FAIL invalid input (test case 1)