QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#470678 | #5416. Fabulous Fungus Frenzy | WRuperD | WA | 0ms | 3692kb | C++14 | 5.4kb | 2024-07-10 15:47:25 | 2024-07-10 15:47:28 |
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;
int change(int x, int y, int x2, int y2){
bool fl = 0;
int op2 = 0;
op now;
while(x < x2){
now.Op(-3, x, y, -1);
swap(s[x][y], s[x + 1][y]);
x++;
ans.pb(now);
op2 = 1;
}
while(x > x2){
now.Op(-4, x, y, -1);
swap(s[x][y], s[x - 1][y]);
x--;
ans.pb(now);
op2 = 2;
}
while(y < y2){
now.Op(-1, x, y, -1);
swap(s[x][y], s[x][y + 1]);
y++;
ans.pb(now);
op2 = 3;
}
while(y > y2){
now.Op(-2, x, y, -1);
swap(s[x][y], s[x][y - 1]);
y--;
op2 = 4;
ans.pb(now);
}
return op2;
}
void exchange(int x, int y, int x2, int 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 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){
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();
}
}
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: 3628kb
input:
3 3 1 OOO GOG BGB OOO GGG BBB 3 1 B G B
output:
26 -3 1 3 -3 1 2 -2 1 2 -1 1 2 -1 1 1 1 1 1 -3 2 2 -2 2 2 -4 3 2 1 1 1 -4 2 2 -2 2 2 -3 1 2 1 1 1 -1 3 2 -3 2 2 -3 1 2 -2 1 2 -2 1 3 -4 2 3 -4 3 3 1 1 1 -1 3 1 -4 2 1 -3 2 1 -3 1 1
result:
ok puzzle solved
Test #2:
score: 0
Accepted
time: 0ms
memory: 3528kb
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: 3692kb
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:
307 2 1 1 -3 3 3 -3 2 3 -2 2 3 -4 3 3 -4 4 3 2 1 1 -3 3 8 -1 3 6 -1 3 5 -1 3 4 -1 3 3 -1 3 2 -4 4 2 -2 4 2 -2 4 3 -2 4 4 -2 4 5 -2 4 6 -2 4 7 -3 3 7 -1 3 6 -1 3 5 -1 3 4 -1 3 2 -3 3 1 -1 2 7 -1 2 6 -1 2 5 -1 2 4 -1 2 3 -1 2 2 -4 3 2 -2 3 2 -2 3 3 -2 3 4 -2 3 5 -2 3 6 -2 3 7 -2 3 8 -3 2 8 -1 2 7 -1 2...
result:
wrong answer puzzle remain unsolved