QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #470757 | #5416. Fabulous Fungus Frenzy | WRuperD | WA | 0ms | 7876kb | C++14 | 6.8kb | 2024-07-10 16:14:32 | 2024-07-10 16:14:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int mininf = 1e9 + 7;
#define int long long
#define pb emplace_back
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');}
#define put() putchar(' ')
#define endl puts("")
const int MAX = 123;
int endt[MAX][MAX];
int cntt[MAX];
int nowctt;
int cntnow[MAX];
int s[MAX][MAX];
struct node{
int n, m;
int s[MAX][MAX];
int cnt[MAX];
int cntnb;
}; node a[MAX];
struct op{
int op, x, y;
int op2;
inline void Op(int op_, int x_, int y_, int op2_){
op = op_, x = x_, y = y_, op2 = op2_;
}
void print(){
write(op), put(), write(x), put(), write(y), endl;
}
};
bool del[MAX];
vector <op> ans;
void change(int x, int y, int x2, int y2){
bool fl = 0;
stack <op> stc;
op now;
while(x < x2){
now.Op(-3, x, y, -1);
swap(s[x][y], s[x + 1][y]);
x++;
ans.pb(now);
stc.push(now);
// op2 = 1;
}
while(x > x2){
now.Op(-4, x, y, -1);
swap(s[x][y], s[x - 1][y]);
x--;
ans.pb(now);
stc.push(now);
}
while(y < y2){
now.Op(-1, x, y, -1);
swap(s[x][y], s[x][y + 1]);
y++;
ans.pb(now);
stc.push(now);
}
while(y > y2){
now.Op(-2, x, y, -1);
swap(s[x][y], s[x][y - 1]);
y--;
stc.push(now);
ans.pb(now);
}
stc.pop();
while(!stc.empty()){
// if(stc.top().[])
if(stc.top().op == -1){
swap(s[stc.top().x][stc.top().y], s[stc.top().x][stc.top().y + 1]);
}else if(stc.top().op == -2){
swap(s[stc.top().x][stc.top().y], s[stc.top().x][stc.top().y - 1]);
}else if(stc.top().op == -3){
swap(s[stc.top().x][stc.top().y], s[stc.top().x + 1][stc.top().y]);
}else{
swap(s[stc.top().x][stc.top().y], s[stc.top().x - 1][stc.top().y]);
}
ans.pb(stc.top());
stc.pop();
}
return ;
}
void exchange(int x, int y, int x2, int y2){
change(x, y, x2, y2);
// int le = change(x, y, x2, y2);
// if(le == 1){
// change(x2 - 1, y2, x, y);
// }
// if(le == 2){
// change(x2 + 1, y2, x, y);
// }
// if(le == 3){
// change(x2, y2 - 1, x, y);
// }
// if(le == 4){
// change(x2, y2 + 1, x, y);
// }
}
int n, m, k;
void print(){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cout<<char(s[i][j]),put();
}endl;
}endl;
}
void print2(){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cout<<char(endt[i][j]),put();
}endl;
}endl;
}
void solve(){
n = read(), m = read(), k = read();
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
char ch;
cin>>ch;
cntt[ch]++;
endt[i][j] = ch;
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
char ch;
cin>>ch;
cntnow[ch]++;
s[i][j] = ch;
}
}
for(int i = 1; i <= k; i++){
a[i].n = read(), a[i].m = read();
for(int j = 1; j <= a[i].n; j++){
for(int k = 1; k <= a[i].m; k++){
char ch;
cin>>ch;
a[i].s[j][k] = ch;
a[i].cnt[ch]++;
}
}
}
while(1){
int nowid = 0;
for(int i = 1; i <= k; i++){
if(del[i]) continue;
int cst = 0;
for(int i2 = 0; i2 < MAX; i2++){
cst += max(0ll, a[i].cnt[i2] - cntnow[i2]);
}
// write(cst), endl;
if(cst > nowctt){
continue;
}
nowid = i;
}
if(!nowid) break;
int nown = a[nowid].n, nowm = a[nowid].m;
for(int i = 1; i <= nown; i++){
for(int j = 1; j <= nowm; j++){
if(s[i][j] != a[nowid].s[i][j]){
bool fll = 0;
for(int i2 = i; i2 <= n; i2++){
for(int j2 = 1; j2 <= m; j2++){
if(i2 == i and j2 <= j) continue;
if(s[i2][j2] == a[nowid].s[i][j]){
exchange(i, j, i2, j2);
fll = 1;
break;
}
}
if(fll) break;
}
if(!fll and s[i][j] != -1){
for(int i2 = i; i2 <= n; i2++){
for(int j2 = 1; j2 <= m; j2++){
if(i2 == i and j2 <= j) continue;
if(s[i2][j2] == -1){
exchange(i, j, i2, j2);
fll = 1;
break;
}
}
if(fll) break;
}
if(!fll) puts("fuckyou1"), print();
}
}
}
}
op nowop;
nowop.Op(nowid, 1, 1, -1);
ans.pb(nowop);
for(int i = 1; i <= nown; i++){
for(int j = 1; j <= nowm; j++){
if(s[i][j] != -1) nowctt++, cntnow[s[i][j]]--;
s[i][j] = -1;
}
}
for(int i = 1; i <= nown; i++){
for(int j = 1; j <= nowm; j++){
if(cntnow[a[nowid].s[i][j]] != 0){
for(int i2 = 1; i2 <= n; i2++){
for(int j2 = 1; j2 <= m; j2++){
if(s[i2][j2] == a[nowid].s[i][j]){
exchange(i2, j2, i, j);
ans.pb(nowop);
cntnow[a[nowid].s[i][j]]--;
nowctt++;
s[i][j] = -1;
}
}
}
}
}
}
// write(nowid), endl;
// print();
del[nowid] = 1;
int cst = 0;
for(int i = 0; i < MAX; i++){
cst += max(0ll, cntt[i] - cntnow[i]);
}
if(cst <= nowctt) break;
}
int cst = 0;
for(int i = 0; i < MAX; i++){
cst += max(0ll, cntt[i] - cntnow[i]);
}
if(cst > nowctt){
puts("-1");
return ;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(s[i][j] == endt[i][j]) continue;
bool flll = 0;
for(int i2 = i; i2 <= n; i2++){
for(int j2 = 1; j2 <= m; j2++){
if(i2 == i and j2 <= j) continue;
if(s[i2][j2] == endt[i][j]){
exchange(i, j, i2, j2);
flll = 1;
break;
}
}
if(flll) break;
}
if(!flll and s[i][j] != -1){
for(int i2 = i; i2 <= n; i2++){
for(int j2 = 1; j2 <= m; j2++){
if(i2 == i and j2 <= j) continue;
if(s[i2][j2] == -1){
exchange(i, j, i2, j2);
flll = 1;
break;
}
}
if(flll) break;
}
// if(!flll) puts("fuckyou2");
}
}
}
// print();
// write(cst), put(), write(nowctt), endl;
write(ans.size()), endl;
for(int i = ans.size() - 1; i >= 0; i--){
ans[i].print();
}
// for(int i = ans.size() - 1; i >= 0; i--){
// if(ans[i].op < 0){
// if(ans[i].op == -1){
// swap(endt[ans[i].x][ans[i].y], endt[ans[i].x][ans[i].y + 1]);
// }else if(ans[i].op == -2){
// swap(endt[ans[i].x][ans[i].y], endt[ans[i].x][ans[i].y - 1]);
// }else if(ans[i].op == -3){
// swap(endt[ans[i].x][ans[i].y], endt[ans[i].x + 1][ans[i].y]);
// }else{
// swap(endt[ans[i].x][ans[i].y], endt[ans[i].x - 1][ans[i].y]);
// }
// }else{
// for(int i2 = 1; i2 <= a[ans[i].op].n; i2++){
// for(int j2 = 1; j2 <= a[ans[i].op].m; j2++){
// endt[i2][j2] = a[ans[i].op].s[i2][j2];
// }
// }
// }
// print2();
// }
}
signed main(){
int t = 1;
while(t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3828kb
input:
3 3 1 OOO GOG BGB OOO GGG BBB 3 1 B G B
output:
26 -3 1 3 -3 2 3 -2 3 3 -3 2 3 -3 1 3 -1 1 2 -1 1 1 1 1 1 -2 2 3 -2 2 2 -2 2 3 1 1 1 -2 2 2 1 1 1 -4 3 3 -4 2 3 -2 1 3 -2 1 2 -2 1 3 -4 2 3 -4 3 3 1 1 1 -1 3 1 -3 1 1 -3 2 1 -3 1 1
result:
ok puzzle solved
Test #2:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
2 2 1 OO OO PP PP 1 2 OP
output:
-1
result:
ok puzzle solved
Test #3:
score: 0
Accepted
time: 0ms
memory: 3664kb
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:
294 2 1 1 -4 4 7 2 1 1 -4 4 8 -4 3 8 -2 2 8 -2 2 7 -2 2 6 -2 2 5 -2 2 4 -2 2 5 -2 2 6 -2 2 7 -2 2 8 -4 3 8 -4 4 8 2 1 1 -3 3 8 -2 4 8 -2 4 7 -2 4 6 -2 4 5 -2 4 6 -2 4 7 -2 4 8 -3 3 8 -3 3 7 -2 4 7 -2 4 6 -2 4 5 -2 4 4 -2 4 3 -2 4 2 -2 4 3 -2 4 4 -2 4 5 -2 4 6 -2 4 7 -3 3 7 -3 3 3 -3 3 1 -3 2 8 -2 3 ...
result:
ok puzzle solved
Test #4:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
2 2 1 OO OO OP PP 1 2 PP
output:
10 -3 1 1 1 1 1 -4 2 2 -2 1 2 -4 2 2 1 1 1 -3 1 2 -2 2 2 -3 1 2 -1 1 1
result:
ok puzzle solved
Test #5:
score: 0
Accepted
time: 0ms
memory: 3816kb
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: 3824kb
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: 3836kb
input:
2 2 1 OO OO OP PP 1 2 OP
output:
7 1 1 1 -4 2 2 1 1 1 -4 2 1 -1 1 1 -4 2 1 1 1 1
result:
ok puzzle solved
Test #8:
score: 0
Accepted
time: 0ms
memory: 7876kb
input:
20 20 20 bofelagiqboebdqplbhq qsrksfthhptcmikjohkt qrnhpoatbekggnkdonet aoalekbmpbisgflbhmol djnhnlitcakltqgegqrt fdctfarsmbnbeosdgilo ttrsljgiratfmioajorh gorljkihdnmnofnblfhm bqjkaehetdjlgctmijpc geslcskpoqjcgtbdspoa riqthroqmmhqgprqhsba fdiarrcomockfqdjjdkd jsbnigfqgsfekbbnnkir ildqctqtqrpcetaocp...
output:
15228 1 1 1 -4 20 15 -4 19 15 -4 18 15 -4 17 15 -4 16 15 -4 15 15 -4 14 15 -4 13 15 -4 12 15 -4 11 15 -4 10 15 -4 9 15 -4 8 15 -4 7 15 -4 6 15 -4 5 15 -4 4 15 -4 3 15 -4 2 15 -2 1 15 -2 1 14 -2 1 13 -2 1 12 -2 1 11 -2 1 10 -2 1 9 -2 1 8 -2 1 7 -2 1 6 -2 1 5 -2 1 4 -2 1 3 -2 1 2 -2 1 3 -2 1 4 -2 1 5 ...
result:
ok puzzle solved
Test #9:
score: 0
Accepted
time: 0ms
memory: 3676kb
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: 0ms
memory: 3864kb
input:
20 20 2 pqo3Mcpvo74RFSsJszsa znrYm92Qr8fbqhbCTOgq 4KiMYr0kLAxPGNG15x7L QHKmq6xaJ4PU4msuRAiv UBfS6VUO87hRnMAjGXKX zCgknw3FfhdifmVcT6FF GH6ohIAzZuprlC3vMDVh mHIJ9KlQvWxt6EgGbJkA 3SwJNhRSdEeF9BNtc9k2 mZmEuriH7Rc4ccMjqI0Y cFfI8TC1iM4PkKziLOiN 15CUjuwudnrums3c3dsl ekL52LiFEpzmU4vaGtuX CfrnQtWb5zAN9oQS2fj...
output:
fuckyou1 E g J
result:
wrong output format Expected integer, but "fuckyou1" found