Submission #37650

#	Time	Username	Problem	Language	Result	Execution time	Memory
37650		SamAnd	Ants (IZhO12_ants)	C++14	100 / 100	403 ms	26816 KiB

ants

#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 (stderr)

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;
             ^

• Subtask 1: 100 / 100