2017 ACM-ICPC World Finals - Rapid City

时间:2022-10-19 18:21:01

希望一年更比一年水

 

Secret Chamber at Mount Rushmore

签到题,搞出可达矩阵就可以了

2017 ACM-ICPC World Finals - Rapid City2017 ACM-ICPC World Finals - Rapid City
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int d[26][26];
 4 
 5 int main() {
 6     int m, n;
 7     scanf("%d %d", &m, &n);
 8     for(int i = 0; i < 26; ++i) d[i][i] = 1;
 9     for(int i = 1; i <= m; ++i) {
10         char a[11], b[11];
11         scanf("%s %s", a, b);
12         d[(a[0] - 'a')][(b[0] - 'a')] = 1;
13     }
14     for(int i = 0; i < 26; ++i)
15         for(int j = 0; j < 26; ++j)
16             for(int k = 0; k < 26; ++k)
17                 d[j][k] |= d[j][i] & d[i][k];
18     for(int i = 1; i <= n; ++i) {
19         char a[111], b[111];
20         scanf("%s %s", a, b);
21         int len1 = strlen(a), len2 = strlen(b), ok = 1;
22         if(len1 != len2) ok = 0;
23         else for(int j = 0; j < len1; ++j) {
24             if(!d[a[j] - 'a'][b[j] - 'a']) {
25                 ok = 0; break;
26             }
27         }
28         puts(ok ? "yes" : "no");
29     }
30     return 0;
31 }
Aguin

 

Need for Speed

又一签到题,二分答案判断总时间是否相等,注意速度不能变负

2017 ACM-ICPC World Finals - Rapid City2017 ACM-ICPC World Finals - Rapid City
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const double eps = 1e-8;
 4 int d[1111], s[1111];
 5 
 6 int main() {
 7     int n, t;
 8     double l = -1e18, r = 1e18;
 9     scanf("%d %d", &n, &t);
10     for(int i = 1; i <= n; ++i) {
11         scanf("%d %d", d + i, s + i);
12         l = max(l, -1.0 * s[i]);
13     }
14     while(r - l > eps) {
15         double m = (l + r) / 2;
16         double sumt = 0;
17         for(int i = 1; i <= n; ++i)
18             sumt += d[i] / (s[i] + m);
19         if(sumt > t) l = m;
20         else r = m;
21     }
22     printf("%.8f\n", l);
23     return 0;
24 }
Aguin

 

Posterize

好像比较正常是一个n3的dp但是我失去理智n4就过了

2017 ACM-ICPC World Finals - Rapid City2017 ACM-ICPC World Finals - Rapid City
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 int r[266], p[266], id[266];
 5 ll f[266][266], g[266][266];
 6 const ll inf = 1e18;
 7 
 8 bool cmp(int i, int j) {
 9     return r[i] < r[j];
10 }
11 
12 int main() {
13     int d, k;
14     scanf("%d %d", &d, &k);
15     for(int i = 1; i <= d; ++i) {
16         scanf("%d %d", r + i, p + i);
17         id[i] = i;
18     }
19     sort(id + 1, id + 1 + d, cmp);
20     for(int i = 0; i < 266; ++i)
21         for(int j = 0; j < 266; ++j)
22                 f[i][j] = inf;
23     f[0][0] = 0;
24     for(int i = 0; i <= 255; ++i) {
25         memcpy(g, f, sizeof(g));
26         for(int j = 0; j <= d; ++j) {
27             for(int l = 0; l < k; ++l) {
28                 if(g[j][l] == inf) continue;
29                 ll sum = 0;
30                 for(int q = 1; j + q <= d; ++q) {
31                     int x = id[j + q];
32                     sum += 1ll * p[x] * (r[x] - i) * (r[x] - i);
33                     f[j + q][l + 1] = min(f[j + q][l + 1], g[j][l] + sum);
34                 }
35             }
36         }
37     }
38     printf("%lld", f[d][k]);
39     return 0;
40 }
Aguin

 

Mission Improbable

好像最大匹配就可以了但是我失去理智最大权匹配就过了

2017 ACM-ICPC World Finals - Rapid City2017 ACM-ICPC World Finals - Rapid City
  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 int a[111][111], rmax[111], cmax[111];
  5 
  6 // SPFA_min_cost_flow
  7 const ll inf = 1e18;
  8 const int maxn = 6e4;
  9 const int maxm = 1e6;
 10 int cnt, h[maxn];
 11 struct edge {
 12     int to, pre, cap, cost;
 13 } e[maxm << 1];
 14 void init() {
 15     cnt = 0;
 16     memset(h, -1, sizeof(h));
 17 }
 18 void add(int from, int to, int cap, int cost) {
 19     e[cnt].pre = h[from];
 20     e[cnt].to = to;
 21     e[cnt].cap = cap;
 22     e[cnt].cost = cost;
 23     h[from] = cnt;
 24     cnt++;
 25 }
 26 ll dist[maxn];
 27 int vis[maxn];
 28 int pv[maxn], pe[maxn];
 29 ll min_cost_flow(int s, int t, int f) {
 30     ll ret = 0;
 31     while (f > 0) {
 32         memset(vis, 0, sizeof(vis));
 33         fill(dist, dist + maxn, inf);
 34         dist[s] = 0;
 35         queue<int> q;
 36         q.push(s);
 37         while (!q.empty()) {
 38             int v = q.front();
 39             q.pop();
 40             vis[v] = 0;
 41             for (int i = h[v]; i >= 0; i = e[i].pre) {
 42                 int to = e[i].to, cap = e[i].cap;
 43                 ll cost = e[i].cost;
 44                 if (cap > 0 && dist[to] > dist[v] + cost) {
 45                     pv[to] = v, pe[to] = i;
 46                     dist[to] = dist[v] + cost;
 47                     if (!vis[to]) q.push(to);
 48                     vis[to] = 1;
 49                 }
 50             }
 51         }
 52 
 53         if (dist[t] > 0) return ret; // modify here
 54 
 55         int d = f;
 56         for (int v = t; v != s; v = pv[v])
 57             d = min(d, e[pe[v]].cap);
 58         f -= d;
 59         ret += d * dist[t];
 60         for (int v = t; v != s; v = pv[v]) {
 61             e[pe[v]].cap -= d;
 62             e[pe[v] ^ 1].cap += d;
 63         }
 64     }
 65     return ret;
 66 }
 67 
 68 int main() {
 69     int r, c;
 70     scanf("%d %d", &r, &c);
 71     ll ans = 0;
 72     for(int i = 1; i <= r; ++i) {
 73         for(int j = 1; j <= c; ++j) {
 74             scanf("%d", &a[i][j]);
 75             if(a[i][j]) ans += a[i][j] - 1;
 76         }
 77     }
 78     init();
 79     int S = r + c + 1, T = S + 1, id = T;
 80     for(int i = 1; i <= r; ++i) {
 81         for(int j = 1; j <= c; ++j) {
 82             rmax[i] = max(rmax[i], a[i][j]);
 83         }
 84         if(rmax[i]) {
 85             ans -= rmax[i] - 1;
 86             add(S, i, 1, 1 - rmax[i]);
 87             add(i, S, 0, rmax[i] - 1);
 88         }
 89     }
 90     for(int j = 1; j <= c; ++j) {
 91         for(int i = 1; i <= r; ++i) {
 92             cmax[j] = max(cmax[j], a[i][j]);
 93         }
 94         if(cmax[j]) {
 95             ans -= cmax[j] - 1;
 96             add(r + j, T, 1, 0);
 97             add(T, r + j, 0, 0);
 98         }
 99     }
100     for(int i = 1; i <= r; ++i) {
101         for(int j = 1; j <= c; ++j) {
102             if(a[i][j] && rmax[i] == cmax[j]) {
103                 ++id;
104                 add(i, id, 1, 0), add(id, i, 0, 0);
105                 add(id, r + j, 1, 0), add(r + j, id, 0, 0);
106             }
107         }
108     }
109     printf("%lld\n", ans - min_cost_flow(S, T, 1e9));
110     return 0;
111 }
Aguin

 

Visual Python++

从上到下扫描线每次匹配最右的不然肯定重叠了,最后检查一遍,注意要处理一下同一行内的重叠

2017 ACM-ICPC World Finals - Rapid City2017 ACM-ICPC World Finals - Rapid City
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 2e5 + 10;
 4 int r[maxn], c[maxn], ans[maxn];
 5 vector<int> bx, by, row[maxn];
 6 map<int, int> col;
 7 map<int, int> :: iterator it;
 8 
 9 typedef pair<int, int> pii;
10 vector<pii> ins[maxn], del[maxn];
11 set<pii> seg, rseg;
12 set<pii> :: iterator itl, itr;
13 inline pii re(pii x) {
14     return pii(-x.second, -x.first);
15 }
16 
17 int main() {
18     int n;
19     scanf("%d", &n);
20     for(int i = 1; i <= n + n; ++i) {
21         scanf("%d %d", r + i, c + i);
22         bx.push_back(r[i]);
23         by.push_back(c[i]);
24     }
25     sort(bx.begin(), bx.end());
26     bx.erase(unique(bx.begin(), bx.end()), bx.end());
27     sort(by.begin(), by.end());
28     by.erase(unique(by.begin(), by.end()), by.end());
29     for(int i = 1; i <= n + n; ++i) {
30         r[i] = lower_bound(bx.begin(), bx.end(), r[i]) - bx.begin() + 1;
31         c[i] = lower_bound(by.begin(), by.end(), c[i]) - by.begin() + 1;
32         row[r[i]].push_back(i);
33     }
34     int ok = 1;
35     for(int i = 1; i <= bx.size(); ++i) {
36         for(int j = 0; j < row[i].size(); ++j) {
37             int x = row[i][j];
38             if(x <= n) {
39                 if(col.find(c[x]) == col.end()) col[c[x]] = x;
40                 else ok = 0;
41             }
42             else {
43                 it = col.upper_bound(c[x]);
44                 if(col.empty() || it == col.begin()) ok = 0;
45                 else {
46                     --it;
47                     int y = (*it).second;
48                     ans[y] = x;
49                     ins[r[y]].emplace_back(pii(c[y], c[x]));
50                     del[r[x]].emplace_back(pii(c[y], c[x]));
51                     col.erase(it);
52                 }
53             }
54         }
55     }
56     if(ok) {
57         for(int i = 1; i <= bx.size(); ++i) {
58             sort(ins[i].begin(), ins[i].end());
59             for(int j = 0; j < ins[i].size(); ++j) {
60                 if(j && ins[i][j].first <= ins[i][j - 1].second) ok = 0;
61                 seg.insert(ins[i][j]), rseg.insert(re(ins[i][j]));
62                 itr = seg.upper_bound(ins[i][j]);
63                 if(itr != seg.end()) {
64                     pii tmp = *itr;
65                     if(tmp.first <= ins[i][j].second) ok = 0;
66                 }
67                 itl = rseg.upper_bound(re(ins[i][j]));
68                 if(itl != seg.end()) {
69                     pii tmp = *itl;
70                     if(tmp.first <= re(ins[i][j]).second) ok = 0;
71                 }
72             }
73             sort(del[i].begin(), del[i].end());
74             for(int j = 0; j < del[i].size(); ++j) {
75                 if(j && del[i][j].first <= del[i][j - 1].second) ok = 0;
76                 seg.erase(del[i][j]), rseg.erase(re(del[i][j]));
77             }
78         }
79     }
80     if(!ok) puts("syntax error");
81     else for(int i = 1; i <= n; ++i) printf("%d\n", ans[i] - n);
82     return 0;
83 }
Aguin

 

Money for Nothing

首先只保留递减的点,然后决策单调性,就可以分治了

2017 ACM-ICPC World Finals - Rapid City2017 ACM-ICPC World Finals - Rapid City
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 1e6 + 10;
 5 int p[maxn], d[maxn], id[maxn];
 6 
 7 bool cmp(int i, int j) {
 8     return d[i] < d[j];
 9 }
10 
11 ll ans;
12 vector<int> L, R;
13 inline ll cal(int i, int j) {
14     return 1ll * (d[R[j]] - d[L[i]]) * (p[R[j]] - p[L[i]]);
15 }
16 void solve(int l1, int r1, int l2, int r2) {
17     if(l2 > r2) return;
18     int m2 = (l2 + r2) / 2;
19     ll mx = -1e18, pos = -1;
20     for(int i = l1; i <= r1; ++i) {
21         if(d[L[i]] >= d[R[m2]]) continue;
22         ll tmp = cal(i, m2);
23         if(tmp > mx) mx = tmp, pos = i;
24     }
25     ans = max(mx, ans);
26     if(l2 != r2) {
27         if(pos == -1) solve(l1, r1, m2 + 1, r2);
28         else solve(l1, pos, l2, m2 - 1), solve(pos, r1, m2 + 1, r2);
29     }
30 }
31 
32 int main() {
33     int m, n;
34     scanf("%d %d", &m, &n);
35     for(int i = 1; i <= m + n; ++i) {
36         scanf("%d %d", p + i, d + i);
37         id[i] = i;
38     }
39     sort(id + 1, id + 1 + m, cmp);
40     for(int i = 1; i <= m; ++i) {
41         if(!L.empty() && p[L.back()] <= p[id[i]]) continue;
42         L.push_back(id[i]);
43     }
44     sort(id + m + 1, id + m + 1 + n, cmp);
45     for(int i = n + m; i >= m + 1; --i) {
46         if(!R.empty() && p[R.back()] >= p[id[i]]) continue;
47         R.push_back(id[i]);
48     }
49     reverse(R.begin(), R.end());
50     solve(0, L.size() - 1, 0, R.size() - 1);
51     printf("%lld\n", ans);
52     return 0;
53 }
Aguin

 

Airport Construction

枚举两个顶点,判断是否是在多边形内且中间没有别的顶点,是的话往两边延伸,比较麻烦的是碰到顶点的情况,更麻烦的是顶点的一边与延伸方向重合的情况……

2017 ACM-ICPC World Finals - Rapid City2017 ACM-ICPC World Finals - Rapid City
  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 typedef long double db;
  5 const db eps=1e-6;
  6 const db inf=1e18;
  7 int sign(db k){
  8     if (k>eps) return 1; else if (k<-eps) return -1; return 0;
  9 }
 10 int cmp(db k1,db k2){return sign(k1-k2);}
 11 int inmid(db k1,db k2,db k3){return sign(k1-k3)*sign(k2-k3)<=0;}// k3 在 [k1,k2] 内
 12 struct point{
 13     db x,y;
 14     point operator + (const point &k1) const{return (point){k1.x+x,k1.y+y};}
 15     point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};}
 16     point operator * (db k1) const{return (point){x*k1,y*k1};}
 17     point operator / (db k1) const{return (point){x/k1,y/k1};}
 18     int operator == (const point &k1) const{return cmp(x,k1.x)==0&&cmp(y,k1.y)==0;}
 19     bool operator < (const point k1) const{
 20         int a=cmp(x,k1.x);
 21         if (a==-1) return 1; else if (a==1) return 0; else return cmp(y,k1.y)==-1;
 22     }
 23     db abs(){return sqrt(x*x+y*y);}
 24 };
 25 int inmid(point k1,point k2,point k3){return inmid(k1.x,k2.x,k3.x)&&inmid(k1.y,k2.y,k3.y);}
 26 db cross(point k1,point k2){return k1.x*k2.y-k1.y*k2.x;}
 27 db dot(point k1,point k2){return k1.x*k2.x+k1.y*k2.y;}
 28 int checkLL(point k1,point k2,point k3,point k4){// 求直线 (L) 线段 (S)k1,k2 和 k3,k4 的交点
 29     return cmp(cross(k3-k1,k4-k1),cross(k3-k2,k4-k2))!=0;
 30 }
 31 point getLL(point k1,point k2,point k3,point k4){
 32     db w1=cross(k1-k3,k4-k3),w2=cross(k4-k3,k2-k3); return (k1*w2+k2*w1)/(w1+w2);
 33 }
 34 int intersect(db l1,db r1,db l2,db r2){
 35     if (l1>r1) swap(l1,r1); if (l2>r2) swap(l2,r2); return cmp(r1,l2)!=-1&&cmp(r2,l1)!=-1;
 36 }
 37 int checkSS(point k1,point k2,point k3,point k4){
 38     return intersect(k1.x,k2.x,k3.x,k4.x)&&intersect(k1.y,k2.y,k3.y,k4.y)&&
 39            sign(cross(k3-k1,k4-k1))*sign(cross(k3-k2,k4-k2))<=0&&
 40            sign(cross(k1-k3,k2-k3))*sign(cross(k1-k4,k2-k4))<=0;
 41 }
 42 int onS(point k1,point k2,point q){return inmid(k1,k2,q)&&sign(cross(k1-q,k2-k1))==0;}
 43 int contain(vector<point>A,point q){ // 2 内部 1 边界 0 外部
 44     int pd=0; A.push_back(A[0]);
 45     for (int i=1;i<A.size();i++){
 46         point u=A[i-1],v=A[i];
 47         if (onS(u,v,q)) return 1; if (cmp(u.y,v.y)>0) swap(u,v);
 48         if (cmp(u.y,q.y)>=0||cmp(v.y,q.y)<0) continue;
 49         if (sign(cross(u-v,q-v))<0) pd^=1;
 50     }
 51     return pd<<1;
 52 }
 53 
 54 int main() {
 55     int n;
 56     scanf("%d", &n);
 57     vector<point> p(n);
 58     for(int i = 0; i < n; ++i) cin >> p[i].x >> p[i].y;
 59     double ans = 0;
 60     for(int i = 0; i < n; ++i) {
 61         for(int j = i + 1; j < n; ++j) {
 62             int ok = 1;
 63             for(int k = 0; k < n; ++k) {
 64                 if(i == k && j == (k + 1) % n || j == k && i == (k + 1) % n) continue;
 65                 if(checkSS(p[i], p[j], p[k], p[(k + 1) % n])) {
 66                     if(onS(p[i], p[j], p[k]) && onS(p[i], p[j], p[(k + 1) % n])) {ok = 0; break;}
 67                     point x = getLL(p[i], p[j], p[k], p[(k + 1) % n]);
 68                     if(x == p[i] || x == p[j]) continue;
 69                     ok = 0; break;
 70                 }
 71             }
 72             point mid = (p[i] + p[j]) / 2;
 73             if(!contain(p, mid)) ok = 0;
 74             if(!ok) continue;
 75             vector<point> q;
 76             for(int k = 0; k < n; ++k) {
 77                 if(checkLL(p[i], p[j], p[k], p[(k + 1) % n])) {
 78                     point x = getLL(p[i], p[j], p[k], p[(k + 1) % n]);
 79                     if(onS(p[k], p[(k + 1) % n], x)) {
 80                         if(x == p[k]) {
 81                             point& nxt = p[(k + 1) % n];
 82                             point& pre = p[(k + n - 1) % n];
 83                             if(sign(cross(p[j] - p[i], pre - p[i])) == 0) {
 84                                 if(sign(dot(p[k] - pre, p[j] - p[i])) > 0 && sign(cross(p[j] - p[i], nxt - p[i])) > 0) q.push_back(x);
 85                                 if(sign(dot(p[k] - pre, p[i] - p[j])) > 0 && sign(cross(p[i] - p[j], nxt - p[j])) > 0) q.push_back(x);
 86                             }
 87                             else {
 88                                 if(sign(cross(p[j] - p[i], pre - p[i])) < 0 && sign(cross(p[j] - p[i], nxt - p[i])) > 0) q.push_back(x);
 89                                 if(sign(cross(p[i] - p[j], pre - p[j])) < 0 && sign(cross(p[i] - p[j], nxt - p[j])) > 0) q.push_back(x);
 90                             }
 91                         }
 92                         else if(x == p[(k + 1) % n]) {
 93                             point& nxt = p[(k + 2) % n];
 94                             point& cur = p[(k + 1) % n];
 95                             if(sign(cross(p[j] - p[i], nxt - p[i])) == 0) {
 96                                 if(sign(dot(nxt - cur, p[j] - p[i])) < 0 && sign(cross(p[j] - p[i], p[k] - p[i])) < 0) q.push_back(x);
 97                                 if(sign(dot(nxt - cur, p[i] - p[j])) < 0 && sign(cross(p[i] - p[j], p[k] - p[j])) < 0) q.push_back(x);
 98                             }
 99                             else {
100                                 if(sign(cross(p[j] - p[i], nxt - p[i])) > 0 && sign(cross(p[j] - p[i], p[k] - p[i])) < 0) q.push_back(x);
101                                 if(sign(cross(p[i] - p[j], nxt - p[j])) > 0 && sign(cross(p[i] - p[j], p[k] - p[j])) < 0) q.push_back(x);
102                             }
103                         }
104                         else q.push_back(x);
105                     }
106                 }
107             }
108             db di = inf, dj = inf;
109             for(int k = 0; k < q.size(); ++k) {
110                 di = min(di, (p[i] - q[k]).abs());
111                 dj = min(dj, (p[j] - q[k]).abs());
112             }
113             ans = max(ans, double((p[i] - p[j]).abs() + di + dj));
114         }
115     }
116     printf("%.8f\n", ans);
117     return 0;
118 }
Aguin

 

Tarot Sham Boast

不会猜结论

2017 ACM-ICPC World Finals - Rapid City2017 ACM-ICPC World Finals - Rapid City
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1e5 + 10;
 4 vector<int> v[11];
 5 string str[11];
 6 char ch[maxn];
 7 int id[11];
 8 
 9 int nxt[maxn];
10 inline void getnxt(int x) {
11     nxt[0] = nxt[1] = 0;
12     int l = str[x].length();
13     for (int i = 1; i < l; i++) {
14         int j = nxt[i];
15         while (j && str[x][i] != str[x][j]) j = nxt[j];
16         nxt[i + 1] = str[x][i] == str[x][j] ? j + 1 : 0;
17     }
18 }
19 
20 bool cmp(int i, int j) {
21     int sz = min(v[i].size(), v[j].size());
22     for(int k = 0; k < sz; ++k) if(v[i][k] != v[j][k]) return v[i][k] > v[j][k];
23     if(v[i].size() != v[j].size()) return v[i].size() < v[j].size();
24     return i < j;
25 }
26 
27 int main() {
28     int n, s;
29     scanf("%d %d", &n, &s);
30     for(int i = 1; i <= s; ++i) {
31         scanf("%s", ch);
32         str[i] = string(ch);
33         getnxt(i);
34         int l = str[i].length(), p = l;
35         while(p) {
36             p = nxt[p];
37             if(l + l - p <= n) v[i].push_back(l + l - p);
38         }
39         id[i] = i;
40     }
41     sort(id + 1, id + 1 + s, cmp);
42     for(int i = 1; i <= s; ++i) printf("%s\n", str[id[i]].c_str());
43     return 0;
44 }
Aguin

 

Replicate Replicate Rfplicbte

不会观察

2017 ACM-ICPC World Finals - Rapid City2017 ACM-ICPC World Finals - Rapid City
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int f[333][333], g[333][333];
 4 
 5 #define F(i, j) ((i < u || j < l) ? 0 : f[i][j])
 6 #define G(i, j) ((i < u || j < l) ? 0 : g[i][j])
 7 inline int check_rows(int u, int d, int l, int r) {
 8     for(int i = u; i <= d + 1; ++i) {
 9         for(int j = l; j <= r + 1; ++j) {
10             g[i][j] = F(i - 1, j - 1);
11             for(int di = -1; di <= 1; ++di) {
12                 for(int dj = -1; dj <= 1; ++dj) {
13                     if(di == 1 && dj == 1) continue;
14                     g[i][j] ^= G(i - 1 + di, j - 1 + dj);
15                 }
16             }
17         }
18         if(g[i][r] || g[i][r + 1]) return i - 1;
19     }
20     return -1;
21 }
22 inline int check_cols(int u, int d, int l, int r) {
23     for(int j = l; j <= r + 1; ++j) {
24         for(int i = u; i <= d + 1; ++i) {
25             g[i][j] = F(i - 1, j - 1);
26             for(int di = -1; di <= 1; ++di) {
27                 for(int dj = -1; dj <= 1; ++dj) {
28                     if(di == 1 && dj == 1) continue;
29                     g[i][j] ^= G(i - 1 + di, j - 1 + dj);
30                 }
31             }
32         }
33         if(g[d][j] || g[d + 1][j]) return j - 1;
34     }
35     return -1;
36 }
37 inline void shrink(int& u, int& d, int& l, int& r) {
38     for(int i = u; i <= d; ++i) {
39         int ok = 1;
40         for(int j = l; j <= r; ++j)
41             if(f[i][j]) ok = 0;
42         if(ok) u++;
43         else break;
44     }
45     for(int i = d; i >= u; --i) {
46         int ok = 1;
47         for(int j = l; j <= r; ++j)
48             if(f[i][j]) ok = 0;
49         if(ok) d--;
50         else break;
51     }
52     for(int j = l; j <= r; ++j) {
53         int ok = 1;
54         for(int i = u; i <= d; ++i)
55             if(f[i][j]) ok = 0;
56         if(ok) l++;
57         else break;
58     }
59     for(int j = r; j >= l; --j) {
60         int ok = 1;
61         for(int i = u; i <= d; ++i)
62             if(f[i][j]) ok = 0;
63         if(ok) r--;
64         else break;
65     }
66 }
67 
68 int main() {
69     int n, m;
70     scanf("%d %d", &m, &n);
71     for(int i = 1; i <= n; ++i) {
72         char s[333];
73         scanf("%s", s + 1);
74         for(int j = 1; j <= m; ++j) f[i][j] = s[j] == '#';
75     }
76     int u = 1, d = n, l = 1, r = m;
77     shrink(u, d, l, r);
78     while(d > u && r > l) {
79         int row = check_rows(u, d, l, r);
80         if(row == -1) memcpy(f, g, sizeof(f));
81         else {
82             int col = check_cols(u, d, l, r);
83             f[row][col] ^= 1;
84             int t = check_rows(u, d, l, r);
85             if(t == -1) memcpy(f, g, sizeof(f));
86             else {f[row][col] ^= 1; break;}
87         }
88         shrink(u, d, l, r);
89     }
90     for(int i = u; i <= d; ++i) {
91         for(int j = l; j <= r; ++j) putchar(f[i][j] ? '#' : '.');
92         puts("");
93     }
94     return 0;
95 }
Aguin