| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 201238 |
2020-02-10T01:30:15 Z |
gs18115 |
여왕벌 (KOI15_queen) |
C++14 |
|
3628 ms |
155604 KB |
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
int op[710][710][3][3][3];
int dp[710][710];
inline void calc(int sz,int mn,int nsz,vector<vector<int> >&in,vector<vector<int> >&in1)
{
in1.clear();
in1.resize(nsz,vector<int>(nsz,0));
for(int i=0;i<sz;i++)
{
for(int j=0;i+j<sz;j++)
{
int ni=min(max(i,mn)-mn,nsz-1);
int nj=min(max(i+j,mn)-mn,nsz-1)-ni;
in1[ni][nj]+=in[i][j];
}
}
return;
}
inline void app(int sz,int mn,int nsz,vector<vector<int> >&in,
vector<vector<pi> >&out,vector<vector<int> >&in1,vector<vector<pi> >&out1)
{
vector<vector<int> >t=in;
in.clear();
in.resize(sz,vector<int>(sz,0));
out.resize(sz,vector<pi>(sz,pi(0,0)));
for(int i=0;i<sz;i++)
{
for(int j=0;i+j<sz;j++)
{
int ni=min(max(i,mn)-mn,nsz-1);
int nj=min(max(i+j,mn)-mn,nsz-1)-ni;
if(ni==0)
{
if(nj==0||nj==nsz-1)
out[i][j]=pi(i,j);
else
out[i][j]=pi(i,mn-i+out1[ni][nj].se);
}
else if(ni+nj==nsz-1)
{
if(ni==0||nj==0)
out[i][j]=pi(i,j);
else
out[i][j]=pi(mn+out1[ni][nj].fi,out1[ni][nj].se+i+j-mn-nsz+1);
}
else
out[i][j]=pi(mn+out1[ni][nj].fi,out1[ni][nj].se);
in[out[i][j].fi][out[i][j].se]+=t[i][j];
}
}
return;
}
vector<vector<pi> >dnc(int s,int e,int l,int r,vector<vector<int> >&in)
{
int sz=r-l+e-s;
vector<vector<pi> >out(sz,vector<pi>(sz,pi(0,0))),o1,o2,o3,o4;
vector<vector<int> >in1;
for(int i=0;i<sz;i++)
for(int j=0;i+j<sz;j++)
out[i][j]=pi(i,j);
if(e<s+2||r<l+2)
return out;
if(e==s+2&&r==l+2)
{
for(int i=0;i<4;i++)
{
for(int j=0;i+j<4;j++)
{
int l2=i>0?0:(i+j>0?1:2);
int d=i>1?0:(i+j>1?1:2);
int u=i>2?0:(i+j>2?1:2);
int nxt=op[s+1][l+1][l2][d][u];
dp[s+1][l+1]+=nxt*in[i][j];
out[i][j]=pi((l2==0)+(nxt==0)+(u==0),(l2==1)+(nxt==1)+(u==1));
}
}
return out;
}
int mx=s+e>>1;
int my=l+r>>1;
int nsz,mn;
nsz=mx-s+my-l+2;
mn=e-mx-1;
calc(sz,mn,nsz,in,in1);
auto out1=dnc(s,mx+1,l,my+1,in1);
app(sz,mn,nsz,in,o1,in1,out1);
nsz=mx-s+r-my+1;
mn=e-mx-1+my-l;
calc(sz,mn,nsz,in,in1);
out1=dnc(s,mx+1,my,r,in1);
app(sz,mn,nsz,in,o2,in1,out1);
nsz=e-mx+my-l+1;
mn=0;
calc(sz,mn,nsz,in,in1);
out1=dnc(mx,e,l,my+1,in1);
app(sz,mn,nsz,in,o3,in1,out1);
nsz=e-mx+r-my;
mn=mx-s;
calc(sz,mn,nsz,in,in1);
out1=dnc(mx,e,my,r,in1);
app(sz,mn,nsz,in,o4,in1,out1);
for(int i=0;i<sz;i++)
{
for(int j=0;i+j<sz;j++)
{
out[i][j]=o1[out[i][j].fi][out[i][j].se];
out[i][j]=o2[out[i][j].fi][out[i][j].se];
out[i][j]=o3[out[i][j].fi][out[i][j].se];
out[i][j]=o4[out[i][j].fi][out[i][j].se];
}
}
return out;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n,q;
cin>>n>>q;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
dp[i][j]=1;
for(int i=1;i<n;i++)
{
for(int j=1;j<n;j++)
{
string s;
cin>>s;
for(int l=0;l<3;l++)
for(int d=0;d<3;d++)
for(int u=0;u<3;u++)
op[i][j][l][d][u]=s[l*9+d*3+u]=='L'?l:(s[l*9+d*3+u]=='D'?d:u);
}
}
int sz=n*2;
vector<vector<int> >in(sz,vector<int>(sz,0));
vector<int>ps(sz,0);
for(int i=0;i<q;i++)
{
int x,y,z;
cin>>x>>y>>z;
in[x][y]++;
ps[x]++;
ps[x+y]++;
}
ps[0]++;
for(int i=1;i<sz;i++)
ps[i]+=ps[i-1];
for(int i=0;i<n;i++)
dp[n-i-1][0]=ps[i];
for(int i=n;i<sz;i++)
dp[0][i-n+1]=ps[i];
dnc(0,n,0,n,in);
for(int i=0;i<n;i++,cout<<endl)
for(int j=0;j<n;j++)
cout<<dp[i][j]<<' ';
return 0;
}
Compilation message
queen.cpp: In function 'std::vector<std::vector<std::pair<int, int> > > dnc(int, int, int, int, std::vector<std::vector<int> >&)':
queen.cpp:94:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mx=s+e>>1;
~^~
queen.cpp:95:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int my=l+r>>1;
~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1663 ms |
80360 KB |
Output isn't correct |
| 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 |
Correct |
5 ms |
408 KB |
Output is correct |
| 4 |
Correct |
5 ms |
380 KB |
Output is correct |
| 5 |
Correct |
220 ms |
6164 KB |
Output is correct |
| 6 |
Correct |
210 ms |
6136 KB |
Output is correct |
| 7 |
Correct |
210 ms |
6156 KB |
Output is correct |
| 8 |
Correct |
199 ms |
6264 KB |
Output is correct |
| 9 |
Incorrect |
3628 ms |
155604 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
