#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e4+2;
const int INF=2e9;
int n,m;
struct doge
{
int p,pos;
bool operator<(const doge& other)
{
if(pos!=other.pos)return pos<other.pos;
return p<=other.p;
}
}d[MAXN];
struct state
{
int pos,p,d;
bool operator<(state const& other)const
{
if(d!=other.d)return d>other.d;
return make_pair(p,pos)<make_pair(other.p,other.pos);
}
};
set<pair<int,int> >doges;
set<int>doges1[MAXN];
vector<pair<int,int> >states;
unordered_map<int,int>dist[MAXN];
unordered_map<int,vector<int> >g[MAXN];
int main()
{
srand(654);
int e=rand();
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
for(int i=0;i<m;++i)
{
cin>>d[i].pos>>d[i].p;
doges.insert({d[i].p,d[i].pos%d[i].p});
doges1[d[i].pos].insert(d[i].p);
}
for(auto t:doges)
{
for(int i=t.second;i<n;i+=t.first)
{
states.push_back({i,t.first});
}
}
for(int i=0;i<n;i++)
{
vector<int>xd;
for(auto ivan:doges1[i])xd.push_back(ivan);
for(int i=0;i<xd.size();i++)
{
if(i!=0)
{
g[i][xd[i]].push_back(xd[i-1]);
}
if(i!=xd.size()-1)
{
g[i][xd[i]].push_back(xd[i+1]);
}
}
}
//dist.reserve(states.size());
for(auto s:states)
{
dist[s.first][(s.second^e)]=INF;
}
deque<state>pq;
pq.push_back({d[0].pos,d[0].p,0});
dist[d[0].pos][d[0].p^e]=0;
while(!pq.empty())
{
state u=pq.front();pq.pop_front();
if(dist[u.pos][u.p^e]<u.d)continue;
if(u.pos==d[1].pos&&u.p==d[1].p)break;
//if(clock()>0.9*CLOCKS_PER_SEC)break;
//cout<<u.pos<<" "<<u.p<<endl;
vector<int>xd=g[u.pos][u.p];
for(int j=0;j<xd.size();j++)
{
auto d1=xd[j];
if(dist[u.pos][d1^e]>u.d)
{
dist[u.pos][d1^e]=u.d;
pq.push_front({u.pos,d1,u.d});
}
}
/* if(it!=doges1[u.pos].begin())
{
--it;
auto d1=(*it);
if(dist[u.pos][d1^e]>u.d)
{
dist[u.pos][d1^e]=u.d;
pq.push_front({u.pos,d1,u.d});
}
++it;
}
//cout<<"**\n";
if(it!=doges1[u.pos].end())++it;
if(it!=doges1[u.pos].end())
{
auto d1=(*it);
if(dist[u.pos][d1^e]>u.d)
{
dist[u.pos][d1^e]=u.d;
pq.push_front({u.pos,d1,u.d});
}
}
}*/
//cout<<"***\n";
/*for(auto d1:doges1[u.pos])
{
if(dist[(u.pos*MAXN+d1)^e]>u.d)
{
dist[(u.pos*MAXN+d1)^e]=u.d;
pq.push({u.pos,d1,u.d});
}
}*/
state v=u;
if(v.pos+v.p<n)
{
v.pos+=v.p;
if(dist[v.pos][v.p^e]>u.d+1)
{
v.d=u.d+1;
dist[v.pos][v.p^e]=v.d;
pq.push_back(v);
}
}
v=u;
if(v.pos-v.p>=0)
{
v.pos-=v.p;
if(dist[v.pos][v.p^e]>u.d+1)
{
v.d=u.d+1;
dist[v.pos][v.p^e]=v.d;
pq.push_back(v);
}
}
}
if(dist[d[1].pos][d[1].p^e]==INF)
{
cout<<-1<<"\n";
}
else cout<<dist[d[1].pos][d[1].p^e]<<"\n";
return 0;
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:54:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i=0;i<xd.size();i++)
| ~^~~~~~~~~~
skyscraper.cpp:60:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | if(i!=xd.size()-1)
| ~^~~~~~~~~~~~~
skyscraper.cpp:82:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for(int j=0;j<xd.size();j++)
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
