#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
#define mp make_pair
struct ban
{
double x,y;
int u;
};
bool operator<(const ban& a,const ban& b)
{
if(a.x<b.x)
return true;
if(a.x>b.x)
return false;
if(a.y<b.y)
return true;
if(a.y>b.y)
return false;
return a.u<b.u;
}
const int T=10003,N=103;
vector<ban> ans[T];
int n,m,tt;
vector<ban> a;
vector<ban> b;
double xx[5]={0,1,0,-1,0};
double yy[5]={0,0,1,0,-1};
int hk[5]={0,3,4,1,2};
pair<pair<double,double>,int> c1(const ban& t)
{
return mp(mp(t.x,t.y),t.u);
}
pair<pair<double,double>,int> c2(const double x,const double y,const int u)
{
return mp(mp(x,y),u);
}
void stg(ban& t)
{
ban h=t;
h.x+=(xx[t.u]/2);
h.y+=(yy[t.u]/2);
if(h.x<0 || h.x>n || h.y<0 || h.y>m)
t.u=hk[t.u];
}
void atob()
{
b.clear();
vector<ban> v;
map<pair<pair<double,double>,int>,bool> c;
for(int i=0;i<a.size();++i)
{
int u=a[i].u;
ban h=a[i];
h.x+=(xx[u]/2);
h.y+=(yy[u]/2);
stg(h);
v.push_back(h);
}
for(int i=0;i<v.size();++i)
c[c1(v[i])]=true;
for(int i=0;i<v.size();++i)
{
ban h=v[i];
int u=h.u;
if(c[c2(h.x,h.y,hk[u])])
{
h.u=hk[u];
}
stg(h);
b.push_back(h);
}
}
/*string hsh(int x)
{
string res;
for(int i=0;i<ans[x].size();++i)
{
int y=ans[x][i].x;
if(!y)
res+='0';
else
{
while(y)
{
res+=char(y%10);
y/=10;
}
}
res+='*';
y=ans[x][i].y;
if(!y)
res+='0';
else
{
while(y)
{
res+=char(y%10);
y/=10;
}
}
res+='*';
y=ans[x][i].u;
if(!y)
res+='0';
else
{
while(y)
{
res+=char(y%10);
y/=10;
}
}
res+='*';
}
}*/
void tp(int x)
{
for(int i=0;i<ans[x].size();++i)
{
cout<<ans[x][i].x<<' '<<ans[x][i].y<<' '<<ans[x][i].u<<endl;
}
}
int main()
{
// freopen("e.in","r",stdin);
// freopen("e.out","w",stdout);
int k;
cin>>n>>m>>k>>tt;
for(int i=0;i<k;++i)
{
ban t;
cin>>t.x>>t.y>>t.u;
a.push_back(t);
}
map<vector<ban>,int> c;
ans[0]=a;
c[a]=0;
int x,y;
for(int i=1;i<=T;++i)
{
a=ans[i-1];
atob();
a=b;
atob();
ans[i]=b;
if(c.find(ans[i])==c.end())
c[ans[i]]=i;
else
{
x=i-1;
y=c[ans[i]];
break;
}
}
if(tt<=x)
{
tp(tt);
return 0;
}
int mo=x-y+1;
tt-=y;
tt%=mo;
tp(tt+y);
return 0;
}
Compilation message
ants.cpp: In function 'void atob()':
ants.cpp:57:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<a.size();++i)
^
ants.cpp:67:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v.size();++i)
^
ants.cpp:70:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v.size();++i)
^
ants.cpp: In function 'void tp(int)':
ants.cpp:129:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ans[x].size();++i)
^
ants.cpp: In function 'int main()':
ants.cpp:175:7: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
tp(tt+y);
^
ants.cpp:172:13: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
int mo=x-y+1;
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
2256 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2256 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2256 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2256 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2256 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2256 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2388 KB |
Output is correct |
| 8 |
Correct |
3 ms |
2388 KB |
Output is correct |
| 9 |
Correct |
6 ms |
2636 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2388 KB |
Output is correct |
| 11 |
Correct |
0 ms |
2388 KB |
Output is correct |
| 12 |
Correct |
6 ms |
2516 KB |
Output is correct |
| 13 |
Correct |
403 ms |
26816 KB |
Output is correct |
| 14 |
Correct |
16 ms |
3312 KB |
Output is correct |
| 15 |
Correct |
0 ms |
2256 KB |
Output is correct |
| 16 |
Correct |
0 ms |
2388 KB |
Output is correct |
| 17 |
Correct |
9 ms |
2760 KB |
Output is correct |
| 18 |
Correct |
13 ms |
3312 KB |
Output is correct |
| 19 |
Correct |
3 ms |
2512 KB |
Output is correct |
| 20 |
Correct |
0 ms |
2256 KB |
Output is correct |
