| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 286890 |
2020-08-31T06:29:07 Z |
문홍윤(#5790) |
None (JOI12_rotate) |
C++17 |
|
1016 ms |
26104 KB |
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(x.begin(), x.end())
#define press(x) x.erase(unique(x.begin(), x.end()), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=2e18;
const int inf=1e9;
struct NODE{
char c;
int link[4];
}nd[2100000];
int n, q, re, num[1010][1010];
char str[1010][1010];
inline int get_dir(int nw, int from){
for(int j=0; j<4; j++){
if(nd[nw].link[j]==from)return j;
}
}
void init_linkedlist(){
for(int i=0; i<=n+1; i++){
for(int j=0; j<=n+1; j++)num[i][j]=++re;
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++)nd[num[i][j]].c=str[i][j];
}
for(int i=0; i<=n; i++){
for(int j=0; j<=n+1; j++){
nd[num[i][j]].link[0]=num[i+1][j];
}
}
for(int i=0; i<=n+1; i++){
for(int j=0; j<=n; j++){
nd[num[i][j]].link[1]=num[i][j+1];
}
}
for(int i=1; i<=n+1; i++){
for(int j=0; j<=n+1; j++){
nd[num[i][j]].link[2]=num[i-1][j];
}
}
for(int i=0; i<=n+1; i++){
for(int j=1; j<=n+1; j++){
nd[num[i][j]].link[3]=num[i][j-1];
}
}
}
vector<int> get_line_y(int x, int sy, int ey){
int prv=num[x][0], nw=nd[num[x][0]].link[1], num=1;
vector<int> ret;
if(sy==0)ret.eb(prv);
while(1){
if(num>ey)return ret;
if(sy<=num)ret.eb(nw);
int to=get_dir(nw, prv);
to=(to+2)%4;
prv=nw;
nw=nd[nw].link[to];
num++;
}
}
vector<int> get_line_x(int y, int sx, int ex){
int prv=num[0][y], nw=nd[num[0][y]].link[0], num=1;
vector<int> ret;
if(sx==0)ret.eb(prv);
while(1){
if(num>ex)return ret;
if(sx<=num)ret.eb(nw);
int to=get_dir(nw, prv);
to=(to+2)%4;
prv=nw;
nw=nd[nw].link[to];
num++;
}
}
void print_linkedlist(){
for(int i=1; i<=n; i++){
vector<int> vc=get_line_y(i, 1, n);
for(auto j:vc)printf("%c", nd[j].c);
puts("");
}
}
void query(int sx, int sy, int ex, int ey){
vector<int> u=get_line_y(sx-1, sy-1, ey+1);
vector<int> d=get_line_y(ex+1, sy-1, ey+1);
vector<int> l=get_line_x(sy-1, sx-1, ex+1);
vector<int> r=get_line_x(ey+1, sx-1, ex+1);
reverse(all(u)); reverse(all(r));
vector<int> u2, d2, l2, r2;
for(int i=1; i<ex-sx+2; i++){
int to=get_dir(l[i], l[i+1]);
to=(to+1)%4;
l2.eb(nd[l[i]].link[to]);
}
for(int i=1; i<ex-sx+2; i++){
int to=get_dir(r[i], r[i+1]);
to=(to+1)%4;
r2.eb(nd[r[i]].link[to]);
}
for(int i=1; i<ex-sx+2; i++){
int to=get_dir(u[i], u[i+1]);
to=(to+1)%4;
u2.eb(nd[u[i]].link[to]);
}
for(int i=1; i<ex-sx+2; i++){
int to=get_dir(d[i], d[i+1]);
to=(to+1)%4;
d2.eb(nd[d[i]].link[to]);
}
for(int i=1; i<ex-sx+2; i++){
int to=get_dir(l[i], l[i+1]);
to=(to+1)%4;
int from=get_dir(l2[i-1], l[i]);
nd[l[i]].link[to]=u2[i-1];
nd[l2[i-1]].link[from]=d[i];
}
for(int i=1; i<ex-sx+2; i++){
int to=get_dir(d[i], d[i+1]);
to=(to+1)%4;
int from=get_dir(d2[i-1], d[i]);
nd[d[i]].link[to]=l2[i-1];
nd[d2[i-1]].link[from]=r[i];
}
for(int i=1; i<ex-sx+2; i++){
int to=get_dir(r[i], r[i+1]);
to=(to+1)%4;
int from=get_dir(r2[i-1], r[i]);
nd[r[i]].link[to]=d2[i-1];
nd[r2[i-1]].link[from]=u[i];
}
for(int i=1; i<ex-sx+2; i++){
int to=get_dir(u[i], u[i+1]);
to=(to+1)%4;
int from=get_dir(u2[i-1], u[i]);
nd[u[i]].link[to]=r2[i-1];
nd[u2[i-1]].link[from]=l[i];
}
}
int main(){
scanf("%d %d", &n, &q);
for(int i=1; i<=n; i++)scanf("%s", str[i]+1);
init_linkedlist();
for(int i=1; i<=q; i++){
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
query(a, b, a+c-1, b+c-1);
}
print_linkedlist();
}
Compilation message
rotate.cpp: In function 'int get_dir(int, int)':
rotate.cpp:30:1: warning: control reaches end of non-void function [-Wreturn-type]
30 | }
| ^
rotate.cpp: In function 'int main()':
rotate.cpp:154:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
154 | scanf("%d %d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~
rotate.cpp:155:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
155 | for(int i=1; i<=n; i++)scanf("%s", str[i]+1);
| ~~~~~^~~~~~~~~~~~~~~~
rotate.cpp:159:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
159 | scanf("%d %d %d", &a, &b, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
615 ms |
25976 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
666 ms |
25936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
698 ms |
25908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
793 ms |
26104 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
838 ms |
25908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
918 ms |
25904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
955 ms |
26012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
980 ms |
25976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1016 ms |
25976 KB |
Output is correct |
