QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#293843 | #5416. Fabulous Fungus Frenzy | huzhaoyang | WA | 1ms | 3756kb | C++14 | 2.0kb | 2023-12-29 20:52:17 | 2023-12-29 20:52:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=25,M=100;
int n,m,k,cnt[M];
char s[N][N];
vector<pair<int,pair<int,int> > >ans;
int get(char c){
if (c=='?')return 62;
if (c<='9')return c-'0';
if (c<='Z')return c-'A'+10;
return c-'a'+36;
}
struct Matrix{
int n,m,cnt[M];
char s[N][N];
void init(){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)cnt[get(s[i][j])]++;
}
}a[N];
void swapD(int x,int y){
swap(s[x][y],s[x+1][y]);
ans.push_back(make_pair(-3,make_pair(x,y)));
}
void swapR(int x,int y){
swap(s[x][y],s[x][y+1]);
ans.push_back(make_pair(-1,make_pair(x,y)));
}
bool check(int k){
int s=0;
for(int i=0;i<62;i++)s+=max(a[k].cnt[i]-cnt[i],0);
if (s>cnt[62])return 0;
for(int i=0;i<62;i++)
if ((a[k].cnt[i])&&(cnt[i]))return 1;
return 0;
}
void calc(int k){
for(int i=1;i<=a[k].n;i++)
for(int j=1;j<=a[k].m;j++){
int c=get(a[k].s[i][j]);
if (!cnt[c])c=62;
for(int x=1;x<=n;x++)
for(int y=1;y<=m;y++)
if ((get(s[x][y])==c)&&((x>i)||(x==i)&&(y>=j))){
while (x<i)swapD(x++,y);
while (y<j)swapR(x,y++);
while (x>i)swapD(--x,y);
while (y>j)swapR(x,--y);
x=y=114514;
}
s[i][j]='?',cnt[c]--,cnt[62]++;
}
if (k)ans.push_back(make_pair(k,make_pair(1,1)));
}
int main(){
scanf("%d%d%d",&n,&m,&k);
a[0].n=n,a[0].m=m;
for(int i=1;i<=n;i++)scanf("%s",a[0].s[i]+1);
for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
for(int t=1;t<=k;t++){
scanf("%d%d",&a[t].n,&a[t].m);
for(int i=1;i<=a[t].n;i++)scanf("%s",a[t].s[i]+1);
}
for(int t=0;t<=k;t++)a[t].init();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)cnt[get(s[i][j])]++;
while (1){
if (check(0)){
calc(0);
break;
}
bool flag=0;
for(int t=1;t<=k;t++)
if (check(t))flag=1,calc(t);
if (!flag){
puts("-1");
return 0;
}
}
printf("%d\n",ans.size());
reverse(ans.begin(),ans.end());
for(pair<int,pair<int,int> >i:ans)printf("%d %d %d\n",i.first,i.second.first,i.second.second);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3592kb
input:
3 3 1 OOO GOG BGB OOO GGG BBB 3 1 B G B
output:
13 -1 3 1 -3 2 3 -1 3 2 -1 2 1 -3 1 3 -1 2 2 -1 1 2 -1 1 1 1 1 1 -1 3 1 -1 2 1 -3 1 1 -3 2 1
result:
ok puzzle solved
Test #2:
score: 0
Accepted
time: 1ms
memory: 3756kb
input:
2 2 1 OO OO PP PP 1 2 OP
output:
-1
result:
ok puzzle solved
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3536kb
input:
4 8 4 11122222 33344444 55556666 77777777 NIxSHUOx DExDUIxx DANxSHIx YUANSHEN 2 3 NIy DEx 3 8 zzzzzzzz DANNSH9I YUA9SHEN 1 1 x 2 5 SHO8y DUUI8
output:
-1
result:
wrong answer solvable puzzle unsolved