SRM 702 Div1
Easyしか解いてないがsystestで落ちた。
結局貪欲に決めていくだけなんだが、行を固定するときに移動元・移動先を固定しないといけなくてそれができてなかった。
具体的には下のコードのused3のところ。
class GridSortMax { public: bool used[51]; bool used2[51]; bool used3[51]; string findMax(int n, int m, vector<int> grid) { vector<vector<int>> fld(n, vector<int>(m, 0)); for(int i : in(n)) for(int j : in(m)) fld[i][j] = grid[i * m + j]; memset(used, 0, sizeof(used)); memset(used3, 0, sizeof(used3)); vector<int> fixed(m, -1); string ans = ""; for(int i : in(n)) { pair<string, int> res(string(m, '.'), -1); for(int j : in(n)) if(!used[j]) { string tmp(m, '0'); for(int k : in(m)) if(i * m + 1 <= fld[j][k] && fld[j][k] <= i * m + m) { int id = fld[j][k] - (i * m + 1); if(fixed[id] != -1) { if(fixed[id] == k) tmp[id] = '1'; } else if(!used3[k]) { tmp[id] = '1'; } } res = max(res, make_pair(tmp, j)); } ans += res.first; int j = res.second; if(res.first != string(m, '0')) used[j] = true; for(int k : in(m)) if(!used3[k]) if(i * m + 1 <= fld[j][k] && fld[j][k] <= i * m + m) { int id = fld[j][k] - (i * m + 1); if(fixed[id] == -1 && !used3[k]) fixed[id] = k, used3[k] = true; } int cntfix = 0, memo = -1; memset(used2, 0, sizeof(used2)); for(int id : in(m)) { if(fixed[id] == -1) cntfix++, memo = id; else used2[fixed[id]] = true; } if(cntfix == 1) { for(int k : in(m)) if(used2[k] == false) fixed[memo] = k; } } return ans; } };
コードが汚なすぎて笑う。
スマートに解いている人もいたが、コードを見ても何をしているのかよくわからなかった。
レートは1210。ついにDiv1ギリギリに来てしまった……。