Submission #200162

#TimeUsernameProblemLanguageResultExecution timeMemory
200162gs14004여왕벌 (KOI15_queen)C++17
10 / 100
5095 ms213292 KiB
#include<bits/stdc++.h> #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() using namespace std; using lint = long long; using pi = pair<int, int>; const int MAXN = 705; struct kek{ int a, b, c, cnt; }; char str[MAXN][MAXN][28]; int n, a[MAXN][MAXN]; vector<pi> get_border(int sx, int ex, int sy, int ey){ vector<pi> v; for(int i=ex; i>=sx; i--) v.emplace_back(i, sy); for(int i=sy+1; i<=ey; i++) v.emplace_back(sx, i); return v; } int aux[4][4]; kek splice(kek i, int l, int r){ auto reduce = [&](int &x, int &y){ int minv = min(x, y); x -= minv; y -= minv; }; int nl = l, nr = i.a + i.b + i.c - r - 1; reduce(nl, i.a); reduce(nl, i.b); reduce(nl, i.c); reduce(nr, i.c); reduce(nr, i.b); reduce(nr, i.a); return i; } kek merge(kek l, kek r, int x, int y){ auto m = splice(l, x, y); kek new_k = {l.a + r.a - m.a, l.b + r.b - m.b, l.c + r.c - m.c, l.cnt}; return new_k; } void solve(int sx, int ex, int sy, int ey, vector<kek> &v){ if(ex - sx <= 1 || ey - sy <= 1){ auto B = get_border(0, ex - sx, 0, ey - sy); for(auto &i : v){ memset(aux, 0, sizeof(aux)); for(int j=i.a; j<i.a + i.b; j++){ aux[B[j].first][B[j].second] = 1; } for(int j=i.a+i.b; j<sz(B); j++){ aux[B[j].first][B[j].second] = 2; } int cc = i.cnt; for(int i=1; i<=ex-sx; i++){ for(int j=1; j<=ey-sy; j++){ int val = aux[i-1][j] + aux[i-1][j-1] * 3 + aux[i][j-1] * 9; char choice = str[i + sx][j + sy][val]; if(choice == 'L') aux[i][j] = aux[i][j-1]; if(choice == 'D') aux[i][j] = aux[i-1][j-1]; if(choice == 'U') aux[i][j] = aux[i-1][j]; a[sx + i][sy + j] += aux[i][j] * cc; } } int c[3] = {}; for(int i=sy; i<=ey; i++) c[aux[ex-sx][i-sy]]++; for(int i=sx; i<ex; i++) c[aux[i-sx][ey-sy]]++; i.a = c[0]; i.b = c[1]; i.c = c[2]; } return; } int mx = (sx + ex) / 2; int my = (sy + ey) / 2; int vec[5] = {0, ex - mx, my - sy + ex - mx, my - sy + ex - sx, ey - sy + ex - sx}; vector<kek> split(sz(v)); for(int i=0; i<sz(v); i++) split[i] = splice(v[i], vec[1], vec[3]); solve(sx, mx, sy, my, split); for(int i=0; i<sz(v); i++) v[i] = merge(v[i], split[i], vec[1], vec[3]); for(int i=0; i<sz(v); i++) split[i] = splice(v[i], vec[2], vec[4]); solve(sx, mx, my, ey, split); for(int i=0; i<sz(v); i++) v[i] = merge(v[i], split[i], vec[2], vec[4]); for(int i=0; i<sz(v); i++) split[i] = splice(v[i], vec[0], vec[2]); solve(mx, ex, sy, my, split); for(int i=0; i<sz(v); i++) v[i] = merge(v[i], split[i], vec[0], vec[2]); vec[1] = my - sy; vec[3] = vec[4] - (mx - sx); for(int i=0; i<sz(v); i++) split[i] = splice(v[i], vec[1], vec[3]); solve(mx, ex, my, ey, split); for(int i=0; i<sz(v); i++) v[i] = merge(v[i], split[i], vec[1], vec[3]); } int main(){ int dx[2 * MAXN] = {}; int q; scanf("%d %d",&n,&q); for(int i=1; i<n; i++){ for(int j=1; j<n; j++){ scanf("%s", str[i][j]); } } vector<kek> v(q); for(auto &i : v){ scanf("%d %d %d",&i.a,&i.b,&i.c); i.cnt = 1; dx[i.a] += 1; dx[i.a + i.b] += 1; } for(int i=1; i<=2*n+2; i++) dx[i] += dx[i-1]; auto vect = get_border(0, n-1, 0, n-1); for(int i=0; i<sz(vect); i++) a[vect[i].first][vect[i].second] += dx[i]; memset(dx, 0, sizeof(dx)); solve(0, n - 1, 0, n - 1, v); for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ printf("%d ", a[i][j] + 1); } puts(""); } }

Compilation message (stderr)

queen.cpp: In function 'int main()':
queen.cpp:96:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
queen.cpp:99:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%s", str[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~
queen.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&i.a,&i.b,&i.c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...