| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 200163 |
2020-02-05T15:06:07 Z |
gs14004 |
여왕벌 (KOI15_queen) |
C++17 |
|
615 ms |
145388 KB |
#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, ra, rb, rc, cnt;
};
int aux[2 * MAXN][2 * MAXN];
vector<kek> compress(vector<kek> &v){
for(auto &i : v){
aux[i.a][i.b] += i.cnt;
}
vector<kek> w;
for(auto &i : v){
if(aux[i.a][i.b]){
w.push_back({i.a, i.b, i.c, aux[i.a][i.b]});
aux[i.a][i.b] = 0;
}
}
return w;
}
void write(vector<kek> &write_pos, vector<kek> &v, vector<kek> &w){
int tot = w[0].a + w[0].b + w[0].c;
for(auto &i : w) aux[i.a][i.b] = (i.ra << 12) + i.rb;
for(int itr = 0; itr < sz(write_pos); itr++){
auto i = v[itr];
int nxta = (aux[i.a][i.b] >> 12);
int nxtb = (aux[i.a][i.b] & 4095);
write_pos[itr].a += nxta - i.a;
write_pos[itr].b += nxtb - i.b;
write_pos[itr].c += (tot - nxta - nxtb) - i.c;
}
for(auto &i : w) aux[i.a][i.b] = 0;
}
char str[MAXN][MAXN][30];
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;
}
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;
}
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){
for(int i=0; i<=ex-sx; i++){
for(int j=0; j<=ey-sy; j++){
aux[i][j] = 0;
}
}
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.a;
i.b = c[1] - i.b;
i.c = c[2] - i.c;
}
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]);
vector<kek> comp = compress(split);
solve(sx, mx, sy, my, comp);
write(v, split, comp);
}
{
vector<kek> split(sz(v));
for(int i=0; i<sz(v); i++) split[i] = splice(v[i], vec[2], vec[4]);
vector<kek> comp = compress(split);
solve(sx, mx, my, ey, comp);
write(v, split, comp);
}
{
vector<kek> split(sz(v));
for(int i=0; i<sz(v); i++) split[i] = splice(v[i], vec[0], vec[2]);
vector<kek> comp = compress(split);
solve(mx, ex, sy, my, comp);
write(v, split, comp);
}
{
vector<kek> split(sz(v));
for(int i=0; i<sz(v); i++) split[i] = splice(v[i], vec[1], vec[3]);
vector<kek> comp = compress(split);
solve(mx, ex, my, ey, comp);
write(v, split, comp);
}
}
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
queen.cpp: In function 'int main()':
queen.cpp:135: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:138: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:143: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 time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
1912 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
1912 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
615 ms |
145388 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
