| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 286893 |
2020-08-31T06:34:47 Z |
문홍윤(#5790) |
None (JOI12_rotate) |
C++17 |
|
74 ms |
50552 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("");
}
}
vector<int> get_close(int sz, vector<int> vc){
vector<int> ret;
for(int i=1; i<sz; i++){
int to=get_dir(vc[i], vc[i+1]);
to=(to+1)%4;
ret.eb(nd[vc[i]].link[to]);
}
return ret;
}
vector<int> connect(int sz, vector<int> l, vector<int> mid, vector<int> midc, vector<int> r){
for(int i=1; i<sz; i++){
int to=get_dir(mid[i], mid[i+1]);
to=(to+1)%4;
int from=get_dir(midc[i-1], mid[i]);
nd[mid[i]].link[to]=l[i-1];
nd[midc[i-1]].link[from]=r[i];
}
}
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=get_close(ex-sx+2, u);
vector<int> d2=get_close(ex-sx+2, d);
vector<int> l2=get_close(ex-sx+2, l);
vector<int> r2=get_close(ex-sx+2, r);
connect(ex-sx+2, u2, l, l2, d);
connect(ex-sx+2, l2, d, d2, r);
connect(ex-sx+2, d2, r, r2, u);
connect(ex-sx+2, r2, u, u2, l);
}
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 'std::vector<int> connect(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
rotate.cpp:113:1: warning: no return statement in function returning non-void [-Wreturn-type]
113 | }
| ^
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:132:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
132 | scanf("%d %d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~
rotate.cpp:133:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
133 | for(int i=1; i<=n; i++)scanf("%s", str[i]+1);
| ~~~~~^~~~~~~~~~~~~~~~
rotate.cpp:137:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
137 | scanf("%d %d %d", &a, &b, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
1920 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
72 ms |
50552 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
72 ms |
50552 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
73 ms |
50552 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
71 ms |
50552 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
70 ms |
50528 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
72 ms |
50552 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
74 ms |
50552 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
71 ms |
50552 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
73 ms |
50552 KB |
Execution killed with signal 11 |
