QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #470670 | #5416. Fabulous Fungus Frenzy | Mathew_Miao | WA | 0ms | 3884kb | C++23 | 7.4kb | 2024-07-10 15:45:42 | 2024-07-10 15:45:43 |
Judging History
answer
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<string>
#include<bitset>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=24;
const int MAXC=128;
const int INF=0x3f3f3f3f;
const long long LINF=0x3f3f3f3f3f3f3f3f;
int n,m,k;
#define node tuple<int,int,int>
basic_string <node> ans;
int px[MAXN],py[MAXN];
char a[MAXN][MAXN];
char c[MAXN][MAXN][MAXN];
int all=0;
int tot[MAXN][MAXC];
int cnt[MAXC];
inline int need(int x){
int res=0;
for(int i=0;i<MAXC;i++)
{
if(tot[x][i]>cnt[i]){
res+=tot[x][i]-cnt[i];
}
}
return res;
}
inline int value(int x){
int res=0;
for(int i=0;i<MAXC;i++)
{
res+=min(tot[x][i],cnt[i]);
}
return res;
}
inline bool check(int x){
return value(x)&&need(x)<=all;
}
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
int id[4]={-4,-3,-2,-1};
inline void swap(int& x,int& y,int d){
ans.push_back(node(id[d],x,y));
swap(a[x][y],a[x+dx[d]][y+dy[d]]);
x+=dx[d];
y+=dy[d];
}
inline void stamp(int x){
for(int i=1;i<=px[x];i++)
{
for(int j=1;j<=py[x];j++)
{
a[i][j]='*';
}
}
ans.push_back(node(x,1,1));
}
#define idx(x,y) (((x)-1)*m+(y))
inline void move(char ch,int x,int y,int p){
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]^ch){
continue;
}
if(i<=px[p]&&j<=py[p]&&idx(i,j)<idx(x,y)){
continue;
}
if(i<=x){
while(i<x)
{
swap(i,j,1);
}
while(j<y)
{
swap(i,j,3);
}
while(j>y)
{
swap(i,j,2);
}
}
else{
while(j<y)
{
swap(i,j,3);
}
while(j>y)
{
swap(i,j,2);
}
while(i>x)
{
swap(i,j,0);
}
}
return ;
}
}
}
inline void work_fir(int x){
for(int i=1;i<=px[x];i++)
{
for(int j=1;j<=py[x];j++)
{
if(cnt[c[x][i][j]]){
move(c[x][i][j],i,j,x);
all++;
cnt[c[x][i][j]]--;
stamp(x);
return ;
}
}
}
}
inline void work(int x){
for(int i=1;i<=px[x];i++)
{
for(int j=1;j<=py[x];j++)
{
if(cnt[c[x][i][j]]){
move(c[x][i][j],i,j,x);
all++;
cnt[c[x][i][j]]--;
}
else{
move('*',i,j,x);
}
}
}
stamp(x);
}
signed main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf(" %c",&c[0][i][j]);
tot[0][c[0][i][j]]++;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf(" %c",&a[i][j]);
cnt[a[i][j]]++;
}
}
for(int t=1;t<=k;t++)
{
scanf("%d%d",&px[t],&py[t]);
for(int i=1;i<=px[t];i++)
{
for(int j=1;j<=py[t];j++)
{
scanf(" %c",&c[t][i][j]);
tot[t][c[t][i][j]]++;
}
}
}
int now=0;
for(int i=1;i<=k;i++)
{
if(check(i)){
now=i;
break;
}
}
while(now)
{
work_fir(now);
while(check(now))
{
work(now);
}
now=0;
for(int i=1;i<=k;i++)
{
if(check(i)){
now=i;
break;
}
}
}
if(need(0)<=all){
if(value(0)){
work_fir(0);
ans.pop_back();
}
printf("%d\n",ans.size());
reverse(ans.begin(),ans.end());
for(auto [opt,x,y]:ans)
{
printf("%d %d %d\n",opt,x,y);
}
}
else{
puts("-1");
}
return 0;
}
/*checker.cpp
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<string>
#include<bitset>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=24+10;
const int N=24;
const int INF=0x3f3f3f3f;
const long long LINF=0x3f3f3f3f3f3f3f3f;
int n,m,k,q;
int px[MAXN],py[MAXN];
char a[MAXN][MAXN],b[MAXN][MAXN];
char c[MAXN][MAXN][MAXN];
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
inline void print(){
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
fprintf(stderr,"%c",a[i][j]);
}
fprintf(stderr,"\n");
}
fprintf(stderr,"\n");
}
inline void swap(int x,int y,int d){
if(x<1||x>n||y<1||y>m){
puts("Swap out of the map!");
exit(0);
}
d+=4;
swap(a[x][y],a[x+dx[d]][y+dy[d]]);
x+=dx[d];
y+=dy[d];
if(x<1||x>n||y<1||y>m){
puts("Swap out of the map!");
exit(0);
}
}
inline void stamp(int x,int y,int p){
if(x<1||x+px[p]-1>n||y<1||y+py[p]-1>m){
puts("Stamp out of the map!");
exit(0);
}
for(int i=x;i<=x+px[p]-1;i++)
{
for(int j=y;j<=y+py[p]-1;j++)
{
a[i][j]=c[p][i-x+1][j-y+1];
}
}
}
signed main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf(" %c",&a[i][j]);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf(" %c",&b[i][j]);
}
}
for(int t=1;t<=k;t++)
{
scanf("%d%d",&px[t],&py[t]);
for(int i=1;i<=px[t];i++)
{
for(int j=1;j<=py[t];j++)
{
scanf(" %c",&c[t][i][j]);
}
}
}
scanf("%d",&q);
while(q--)
{
int opt,x,y;
scanf("%d%d%d",&opt,&x,&y);
if(opt<-4||opt==0||opt>k){
puts("What are you doing?!");
return 0;
}
if(opt>0){
stamp(x,y,opt);
}
else if(opt>=-4){
swap(x,y,opt);
}
else{
puts("I don't write rotate...");
return 0;
}
}
bool flg=true;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]!=b[i][j]){
puts("Puzzle remain unsolved.");
flg=false;
break;
}
}
if(!flg){
break;
}
}
if(flg){
puts("Accepted!");
}
else{
puts("particle result:");
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
putchar(a[i][j]);
}
putchar('\n');
}
putchar('\n');
}
return 0;
}
*/
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3884kb
input:
3 3 1 OOO GOG BGB OOO GGG BBB 3 1 B G B
output:
17 -2 3 2 -3 2 2 1 1 1 -2 3 2 -3 2 2 -2 2 2 -2 2 3 1 1 1 -2 3 2 -2 3 3 -2 2 2 -4 2 1 -4 3 1 -2 3 2 1 1 1 -4 2 1 -4 3 1
result:
wrong answer puzzle remain unsolved