QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#293847 | #5416. Fabulous Fungus Frenzy | huzhaoyang | WA | 2ms | 3880kb | C++14 | 2.0kb | 2023-12-29 20:55:59 | 2023-12-29 20:56:01 |
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;
if (!k)return 1;
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: 3580kb
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: 0ms
memory: 3568kb
input:
2 2 1 OO OO PP PP 1 2 OP
output:
-1
result:
ok puzzle solved
Test #3:
score: 0
Accepted
time: 1ms
memory: 3880kb
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:
122 3 1 1 -1 1 1 -1 1 2 -1 1 3 -1 1 4 -1 1 5 -1 1 6 -1 1 7 -3 1 8 -3 2 8 -3 3 8 1 1 1 -1 2 3 -1 2 4 -1 2 5 -1 2 6 -3 2 7 -3 3 7 3 1 1 -1 1 1 -1 1 2 -1 1 3 -3 1 4 -3 2 4 -3 3 4 2 1 1 -3 3 6 -3 3 5 -3 3 3 -1 4 2 -1 3 2 -1 3 3 -1 3 4 -1 3 5 -1 3 6 -1 3 7 -3 3 1 -3 2 6 -3 2 5 -1 2 4 -1 2 5 -1 2 6 -1 2 7...
result:
ok puzzle solved
Test #4:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
2 2 1 OO OO OP PP 1 2 PP
output:
8 -1 1 1 -3 1 2 1 1 1 -3 1 1 1 1 1 -3 1 2 -1 2 1 -1 1 1
result:
ok puzzle solved
Test #5:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
2 2 1 OO OO OP PO 2 1 P P
output:
4 -3 1 2 -1 1 1 1 1 1 -1 1 1
result:
ok puzzle solved
Test #6:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
2 2 1 OO OO OP PO 2 2 PP PP
output:
-1
result:
ok puzzle solved
Test #7:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
2 2 1 OO OO OP PP 1 2 OP
output:
7 1 1 1 -3 1 2 -1 2 1 1 1 1 -3 1 2 -1 2 1 1 1 1
result:
ok puzzle solved
Test #8:
score: 0
Accepted
time: 2ms
memory: 3736kb
input:
20 20 20 bofelagiqboebdqplbhq qsrksfthhptcmikjohkt qrnhpoatbekggnkdonet aoalekbmpbisgflbhmol djnhnlitcakltqgegqrt fdctfarsmbnbeosdgilo ttrsljgiratfmioajorh gorljkihdnmnofnblfhm bqjkaehetdjlgctmijpc geslcskpoqjcgtbdspoa riqthroqmmhqgprqhsba fdiarrcomockfqdjjdkd jsbnigfqgsfekbbnnkir ildqctqtqrpcetaocp...
output:
8497 8 1 1 -1 1 1 -1 1 2 -1 1 3 -1 1 4 -1 1 5 -1 1 6 -1 1 7 -1 1 8 -1 1 9 -1 1 10 -1 1 11 -1 1 12 -3 1 13 -3 2 13 -3 3 13 -3 4 13 -3 5 13 -3 6 13 -3 7 13 -3 8 13 -3 9 13 -3 10 13 -3 11 13 -3 12 13 -3 13 13 -3 14 13 -3 15 13 -3 16 13 -3 17 13 -3 18 13 -3 19 13 8 1 1 -1 1 1 -1 1 2 -1 1 3 -1 1 4 -1 1 5...
result:
ok puzzle solved
Test #9:
score: 0
Accepted
time: 0ms
memory: 3432kb
input:
20 20 2 HbevPluVL5ORtUFcV9gf Mrq6zdTPMPnwlN7Fpzx6 Nfp71dVuxTZp9Qet0Ca9 ugbaF34DquDdbUnk5x7V fDFszn4PmvMpJ5BDWueJ 2YvFxKJgst8XbftPfy9T F7Q4huk87Lrp1M7i08is Q41E5AqLkkP3Q5qONXC2 MuM7iIzev3ZpxItvriQK 6OBdEC0sso5vdNQlrCSR BJQtKjN6RmppsMGIYL81 yyKsWJSoKorGGblNle0r RkKEQACh8f0bS5nPTtJH fQgoc39vdsPAUmxlYYL...
output:
-1
result:
ok puzzle solved
Test #10:
score: -100
Wrong Answer
time: 2ms
memory: 3824kb
input:
20 20 2 pqo3Mcpvo74RFSsJszsa znrYm92Qr8fbqhbCTOgq 4KiMYr0kLAxPGNG15x7L QHKmq6xaJ4PU4msuRAiv UBfS6VUO87hRnMAjGXKX zCgknw3FfhdifmVcT6FF GH6ohIAzZuprlC3vMDVh mHIJ9KlQvWxt6EgGbJkA 3SwJNhRSdEeF9BNtc9k2 mZmEuriH7Rc4ccMjqI0Y cFfI8TC1iM4PkKziLOiN 15CUjuwudnrums3c3dsl ekL52LiFEpzmU4vaGtuX CfrnQtWb5zAN9oQS2fj...
output:
5586 -1 20 7 -1 20 8 -1 20 9 -1 20 10 -1 20 11 -1 20 12 -1 20 13 -1 20 14 -1 20 15 -1 20 16 -1 20 6 -1 20 7 -1 20 8 -1 20 9 -1 20 10 -1 20 11 -1 20 12 -1 20 5 -1 20 6 -1 20 7 -1 20 8 -1 20 9 -1 20 10 -1 20 4 -1 20 5 -1 20 6 -1 20 7 -1 20 8 -1 20 3 -1 20 4 -1 20 5 -1 20 6 -1 20 2 -1 20 3 -1 20 4 -1 2...
result:
wrong answer puzzle remain unsolved