oj.uz

Submission #338774

# Submission time Handle Problem Language Result Execution time Memory
338774 2020-12-23T21:17:27 Z ogibogi2004 Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 1000 ms 101648 KB 
#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];
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});
		}
	}
	//dist.reserve(states.size());
	for(auto s:states)
	{
		dist[s.first][(s.second^e)]=INF;
	}
	priority_queue<state>pq;
	pq.push({d[0].pos,d[0].p,0});
	dist[d[0].pos][d[0].p^e]=0;
	while(!pq.empty())
	{
		state u=pq.top();pq.pop();
		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;
		if(doges1[u.pos].size()>0)
		{
			auto it=doges1[u.pos].lower_bound(u.p);
			if(it!=doges1[u.pos].end()&&(*it)!=u.p)
			{
				auto d1=(*it);
				if(dist[u.pos][d1^e]>u.d)
				{
					dist[u.pos][d1^e]=u.d;
					pq.push({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({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({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(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(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;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3436 KB Output is correct
2 Correct 2 ms 3436 KB Output is correct
3 Correct 2 ms 3436 KB Output is correct
4 Correct 4 ms 3564 KB Output is correct
5 Correct 2 ms 3436 KB Output is correct
6 Correct 2 ms 3436 KB Output is correct
7 Correct 2 ms 3436 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3364 KB Output is correct
2 Correct 2 ms 3436 KB Output is correct
3 Correct 2 ms 3436 KB Output is correct
4 Correct 2 ms 3436 KB Output is correct
5 Correct 2 ms 3436 KB Output is correct
6 Correct 2 ms 3436 KB Output is correct
7 Correct 2 ms 3436 KB Output is correct
8 Correct 2 ms 3436 KB Output is correct
9 Correct 2 ms 3436 KB Output is correct
10 Correct 3 ms 3564 KB Output is correct
11 Correct 4 ms 3820 KB Output is correct
12 Correct 3 ms 3436 KB Output is correct
13 Correct 2 ms 3436 KB Output is correct
14 Correct 6 ms 3948 KB Output is correct
15 Correct 6 ms 3948 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3436 KB Output is correct
2 Correct 2 ms 3436 KB Output is correct
3 Correct 2 ms 3436 KB Output is correct
4 Correct 2 ms 3436 KB Output is correct
5 Correct 2 ms 3436 KB Output is correct
6 Correct 2 ms 3436 KB Output is correct
7 Correct 2 ms 3436 KB Output is correct
8 Correct 2 ms 3436 KB Output is correct
9 Correct 2 ms 3436 KB Output is correct
10 Correct 3 ms 3564 KB Output is correct
11 Correct 4 ms 3820 KB Output is correct
12 Correct 3 ms 3436 KB Output is correct
13 Correct 3 ms 3436 KB Output is correct
14 Correct 6 ms 3948 KB Output is correct
15 Correct 5 ms 3948 KB Output is correct
16 Correct 3 ms 3692 KB Output is correct
17 Correct 7 ms 4332 KB Output is correct
18 Correct 5 ms 3820 KB Output is correct
19 Correct 4 ms 3692 KB Output is correct
20 Correct 3 ms 3712 KB Output is correct
21 Correct 4 ms 3820 KB Output is correct
22 Correct 4 ms 3820 KB Output is correct
23 Correct 5 ms 3820 KB Output is correct
24 Correct 7 ms 4204 KB Output is correct
25 Correct 5 ms 3948 KB Output is correct
26 Correct 4 ms 3820 KB Output is correct
27 Correct 4 ms 3820 KB Output is correct
28 Correct 11 ms 4840 KB Output is correct
29 Correct 29 ms 6628 KB Output is correct
30 Correct 8 ms 4336 KB Output is correct
31 Correct 16 ms 5220 KB Output is correct
32 Correct 12 ms 4840 KB Output is correct
33 Correct 64 ms 9952 KB Output is correct
34 Correct 51 ms 9952 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3436 KB Output is correct
2 Correct 2 ms 3436 KB Output is correct
3 Correct 2 ms 3436 KB Output is correct
4 Correct 2 ms 3436 KB Output is correct
5 Correct 2 ms 3436 KB Output is correct
6 Correct 3 ms 3436 KB Output is correct
7 Correct 2 ms 3436 KB Output is correct
8 Correct 2 ms 3436 KB Output is correct
9 Correct 2 ms 3436 KB Output is correct
10 Correct 3 ms 3564 KB Output is correct
11 Correct 4 ms 3820 KB Output is correct
12 Correct 3 ms 3436 KB Output is correct
13 Correct 3 ms 3436 KB Output is correct
14 Correct 6 ms 3948 KB Output is correct
15 Correct 5 ms 3948 KB Output is correct
16 Correct 3 ms 3692 KB Output is correct
17 Correct 7 ms 4332 KB Output is correct
18 Correct 5 ms 3820 KB Output is correct
19 Correct 4 ms 3692 KB Output is correct
20 Correct 4 ms 3692 KB Output is correct
21 Correct 3 ms 3692 KB Output is correct
22 Correct 4 ms 3820 KB Output is correct
23 Correct 5 ms 3820 KB Output is correct
24 Correct 10 ms 4204 KB Output is correct
25 Correct 5 ms 3948 KB Output is correct
26 Correct 4 ms 3820 KB Output is correct
27 Correct 4 ms 3820 KB Output is correct
28 Correct 10 ms 4840 KB Output is correct
29 Correct 29 ms 6628 KB Output is correct
30 Correct 8 ms 4336 KB Output is correct
31 Correct 16 ms 5220 KB Output is correct
32 Correct 12 ms 4840 KB Output is correct
33 Correct 62 ms 9952 KB Output is correct
34 Correct 50 ms 9952 KB Output is correct
35 Correct 70 ms 11492 KB Output is correct
36 Correct 9 ms 4840 KB Output is correct
37 Correct 76 ms 14172 KB Output is correct
38 Correct 76 ms 14432 KB Output is correct
39 Correct 78 ms 14304 KB Output is correct
40 Correct 76 ms 14436 KB Output is correct
41 Correct 105 ms 14944 KB Output is correct
42 Correct 9 ms 4076 KB Output is correct
43 Correct 9 ms 4076 KB Output is correct
44 Correct 7 ms 3820 KB Output is correct
45 Correct 410 ms 32468 KB Output is correct
46 Correct 338 ms 32468 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3564 KB Output is correct
2 Correct 2 ms 3436 KB Output is correct
3 Correct 2 ms 3436 KB Output is correct
4 Correct 2 ms 3436 KB Output is correct
5 Correct 2 ms 3436 KB Output is correct
6 Correct 2 ms 3436 KB Output is correct
7 Correct 2 ms 3436 KB Output is correct
8 Correct 2 ms 3436 KB Output is correct
9 Correct 3 ms 3436 KB Output is correct
10 Correct 3 ms 3564 KB Output is correct
11 Correct 4 ms 3820 KB Output is correct
12 Correct 3 ms 3436 KB Output is correct
13 Correct 3 ms 3436 KB Output is correct
14 Correct 6 ms 3948 KB Output is correct
15 Correct 6 ms 3948 KB Output is correct
16 Correct 3 ms 3692 KB Output is correct
17 Correct 7 ms 4332 KB Output is correct
18 Correct 4 ms 3820 KB Output is correct
19 Correct 3 ms 3692 KB Output is correct
20 Correct 3 ms 3692 KB Output is correct
21 Correct 3 ms 3692 KB Output is correct
22 Correct 4 ms 3820 KB Output is correct
23 Correct 5 ms 3820 KB Output is correct
24 Correct 9 ms 4204 KB Output is correct
25 Correct 5 ms 3948 KB Output is correct
26 Correct 4 ms 3820 KB Output is correct
27 Correct 4 ms 3820 KB Output is correct
28 Correct 10 ms 4840 KB Output is correct
29 Correct 31 ms 6628 KB Output is correct
30 Correct 8 ms 4336 KB Output is correct
31 Correct 17 ms 5220 KB Output is correct
32 Correct 13 ms 4840 KB Output is correct
33 Correct 58 ms 9952 KB Output is correct
34 Correct 49 ms 9952 KB Output is correct
35 Correct 68 ms 11492 KB Output is correct
36 Correct 9 ms 4840 KB Output is correct
37 Correct 71 ms 14300 KB Output is correct
38 Correct 74 ms 14432 KB Output is correct
39 Correct 73 ms 14304 KB Output is correct
40 Correct 77 ms 14436 KB Output is correct
41 Correct 101 ms 14944 KB Output is correct
42 Correct 9 ms 4076 KB Output is correct
43 Correct 9 ms 4076 KB Output is correct
44 Correct 7 ms 3820 KB Output is correct
45 Correct 439 ms 32468 KB Output is correct
46 Correct 323 ms 32468 KB Output is correct
47 Correct 498 ms 44880 KB Output is correct
48 Correct 114 ms 17892 KB Output is correct
49 Correct 65 ms 13024 KB Output is correct
50 Correct 57 ms 12380 KB Output is correct
51 Correct 192 ms 23124 KB Output is correct
52 Correct 233 ms 24788 KB Output is correct
53 Correct 45 ms 11232 KB Output is correct
54 Correct 9 ms 5488 KB Output is correct
55 Correct 13 ms 6508 KB Output is correct
56 Correct 19 ms 7144 KB Output is correct
57 Correct 202 ms 26584 KB Output is correct
58 Correct 25 ms 7400 KB Output is correct
59 Correct 34 ms 8680 KB Output is correct
60 Correct 46 ms 10088 KB Output is correct
61 Correct 44 ms 9720 KB Output is correct
62 Correct 458 ms 31828 KB Output is correct
63 Execution timed out 1090 ms 101648 KB Time limit exceeded
64 Halted 0 ms 0 KB -