oj.uz

Submission #338745

# Submission time Handle Problem Language Result Execution time Memory
338745 2020-12-23T19:33:59 Z ogibogi2004 Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 417 ms 262148 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e4+12;
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<int>states;
unordered_map<int,int>dist;
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*MAXN+t.first);
		}
	}
	dist.reserve(states.size()+1);
	dist.max_load_factor(0.125);
	for(auto s:states)
	{
		dist[(s^e)]=INF;
	}
	priority_queue<state>pq;
	pq.push({d[0].pos,d[0].p,0});
	dist[(d[0].pos*MAXN+d[0].p)^e]=0;
	while(!pq.empty())
	{
		state u=pq.top();pq.pop();
		if(dist[(u.pos*MAXN+u.p)^e]<u.d)continue;
		if(u.pos==d[1].pos&&u.p==d[1].p)break;
		doges1[u.pos].erase(u.p);
		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>=0)
		{
			v.pos-=v.p;
			if(dist[(v.pos*MAXN+v.p)^e]>u.d+1)
			{
				v.d=u.d+1;
				dist[(v.pos*MAXN+v.p)^e]=v.d;
				pq.push(v);
			}
		}
		v=u;
		if(v.pos+v.p<n)
		{
			v.pos+=v.p;
			if(dist[(v.pos*MAXN+v.p)^e]>u.d+1)
			{
				v.d=u.d+1;
				dist[(v.pos*MAXN+v.p)^e]=v.d;
				pq.push(v);
			}
		}
	}
	if(dist[(d[1].pos*MAXN+d[1].p)^e]==INF)
	{
		cout<<-1<<"\n";
	}
	else cout<<dist[(d[1].pos*MAXN+d[1].p)^e]<<"\n";
return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1772 KB Output is correct
2 Correct 1 ms 1772 KB Output is correct
3 Correct 1 ms 1772 KB Output is correct
4 Correct 1 ms 1772 KB Output is correct
5 Correct 1 ms 1772 KB Output is correct
6 Correct 2 ms 1772 KB Output is correct
7 Correct 1 ms 1772 KB Output is correct
8 Correct 1 ms 1772 KB Output is correct
9 Correct 1 ms 1772 KB Output is correct
10 Correct 2 ms 2028 KB Output is correct
11 Correct 3 ms 2540 KB Output is correct
12 Correct 2 ms 1772 KB Output is correct
13 Correct 2 ms 1772 KB Output is correct
14 Correct 15 ms 2836 KB Output is correct
15 Correct 7 ms 2792 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1772 KB Output is correct
2 Correct 1 ms 1772 KB Output is correct
3 Correct 2 ms 1772 KB Output is correct
4 Correct 1 ms 1772 KB Output is correct
5 Correct 1 ms 1772 KB Output is correct
6 Correct 1 ms 1772 KB Output is correct
7 Correct 1 ms 1772 KB Output is correct
8 Correct 2 ms 1772 KB Output is correct
9 Correct 2 ms 1772 KB Output is correct
10 Correct 2 ms 2028 KB Output is correct
11 Correct 4 ms 2540 KB Output is correct
12 Correct 2 ms 1772 KB Output is correct
13 Correct 2 ms 1772 KB Output is correct
14 Correct 5 ms 2792 KB Output is correct
15 Correct 5 ms 2792 KB Output is correct
16 Correct 3 ms 2284 KB Output is correct
17 Correct 6 ms 3704 KB Output is correct
18 Correct 3 ms 2784 KB Output is correct
19 Correct 2 ms 2412 KB Output is correct
20 Correct 2 ms 2156 KB Output is correct
21 Correct 2 ms 2284 KB Output is correct
22 Correct 3 ms 2540 KB Output is correct
23 Correct 4 ms 2784 KB Output is correct
24 Correct 7 ms 3484 KB Output is correct
25 Correct 4 ms 2920 KB Output is correct
26 Correct 3 ms 2796 KB Output is correct
27 Correct 4 ms 2656 KB Output is correct
28 Correct 8 ms 4776 KB Output is correct
29 Correct 26 ms 9124 KB Output is correct
30 Correct 8 ms 3908 KB Output is correct
31 Correct 14 ms 5716 KB Output is correct
32 Correct 11 ms 4648 KB Output is correct
33 Correct 64 ms 16820 KB Output is correct
34 Correct 48 ms 16820 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1772 KB Output is correct
2 Correct 1 ms 1772 KB Output is correct
3 Correct 1 ms 1772 KB Output is correct
4 Correct 1 ms 1772 KB Output is correct
5 Correct 1 ms 1772 KB Output is correct
6 Correct 1 ms 1772 KB Output is correct
7 Correct 1 ms 1772 KB Output is correct
8 Correct 1 ms 1772 KB Output is correct
9 Correct 1 ms 1772 KB Output is correct
10 Correct 2 ms 2028 KB Output is correct
11 Correct 3 ms 2540 KB Output is correct
12 Correct 2 ms 1772 KB Output is correct
13 Correct 2 ms 1772 KB Output is correct
14 Correct 5 ms 2792 KB Output is correct
15 Correct 5 ms 2792 KB Output is correct
16 Correct 2 ms 2284 KB Output is correct
17 Correct 6 ms 3704 KB Output is correct
18 Correct 3 ms 2784 KB Output is correct
19 Correct 2 ms 2412 KB Output is correct
20 Correct 2 ms 2156 KB Output is correct
21 Correct 2 ms 2284 KB Output is correct
22 Correct 3 ms 2540 KB Output is correct
23 Correct 4 ms 2784 KB Output is correct
24 Correct 6 ms 3484 KB Output is correct
25 Correct 4 ms 2920 KB Output is correct
26 Correct 3 ms 2796 KB Output is correct
27 Correct 4 ms 2656 KB Output is correct
28 Correct 9 ms 4776 KB Output is correct
29 Correct 26 ms 9124 KB Output is correct
30 Correct 8 ms 3908 KB Output is correct
31 Correct 15 ms 5716 KB Output is correct
32 Correct 10 ms 4648 KB Output is correct
33 Correct 57 ms 16820 KB Output is correct
34 Correct 43 ms 16820 KB Output is correct
35 Correct 75 ms 17004 KB Output is correct
36 Correct 8 ms 4516 KB Output is correct
37 Correct 72 ms 24048 KB Output is correct
38 Correct 75 ms 25060 KB Output is correct
39 Correct 65 ms 25060 KB Output is correct
40 Correct 68 ms 25064 KB Output is correct
41 Correct 99 ms 25060 KB Output is correct
42 Correct 8 ms 3052 KB Output is correct
43 Correct 8 ms 2912 KB Output is correct
44 Correct 7 ms 2284 KB Output is correct
45 Correct 369 ms 61520 KB Output is correct
46 Correct 311 ms 61532 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1772 KB Output is correct
2 Correct 1 ms 1772 KB Output is correct
3 Correct 1 ms 1772 KB Output is correct
4 Correct 1 ms 1772 KB Output is correct
5 Correct 1 ms 1772 KB Output is correct
6 Correct 1 ms 1772 KB Output is correct
7 Correct 1 ms 1772 KB Output is correct
8 Correct 2 ms 1900 KB Output is correct
9 Correct 2 ms 1772 KB Output is correct
10 Correct 2 ms 2028 KB Output is correct
11 Correct 3 ms 2540 KB Output is correct
12 Correct 2 ms 1772 KB Output is correct
13 Correct 2 ms 1772 KB Output is correct
14 Correct 5 ms 2792 KB Output is correct
15 Correct 5 ms 2792 KB Output is correct
16 Correct 2 ms 2284 KB Output is correct
17 Correct 6 ms 3704 KB Output is correct
18 Correct 3 ms 2784 KB Output is correct
19 Correct 2 ms 2412 KB Output is correct
20 Correct 3 ms 2156 KB Output is correct
21 Correct 2 ms 2284 KB Output is correct
22 Correct 3 ms 2540 KB Output is correct
23 Correct 4 ms 2784 KB Output is correct
24 Correct 6 ms 3484 KB Output is correct
25 Correct 4 ms 2920 KB Output is correct
26 Correct 3 ms 2796 KB Output is correct
27 Correct 4 ms 2676 KB Output is correct
28 Correct 8 ms 4776 KB Output is correct
29 Correct 26 ms 9124 KB Output is correct
30 Correct 8 ms 3908 KB Output is correct
31 Correct 14 ms 5716 KB Output is correct
32 Correct 10 ms 4648 KB Output is correct
33 Correct 61 ms 16820 KB Output is correct
34 Correct 53 ms 16820 KB Output is correct
35 Correct 78 ms 17004 KB Output is correct
36 Correct 8 ms 4516 KB Output is correct
37 Correct 68 ms 24032 KB Output is correct
38 Correct 79 ms 25060 KB Output is correct
39 Correct 68 ms 25060 KB Output is correct
40 Correct 67 ms 25064 KB Output is correct
41 Correct 97 ms 25060 KB Output is correct
42 Correct 8 ms 3052 KB Output is correct
43 Correct 8 ms 2912 KB Output is correct
44 Correct 7 ms 2284 KB Output is correct
45 Correct 367 ms 61520 KB Output is correct
46 Correct 301 ms 61520 KB Output is correct
47 Correct 256 ms 94952 KB Output is correct
48 Correct 78 ms 31996 KB Output is correct
49 Correct 55 ms 21304 KB Output is correct
50 Correct 50 ms 20660 KB Output is correct
51 Correct 148 ms 42968 KB Output is correct
52 Correct 167 ms 46168 KB Output is correct
53 Correct 44 ms 15704 KB Output is correct
54 Correct 9 ms 5392 KB Output is correct
55 Correct 16 ms 8476 KB Output is correct
56 Correct 19 ms 7056 KB Output is correct
57 Correct 131 ms 54320 KB Output is correct
58 Correct 29 ms 9904 KB Output is correct
59 Correct 36 ms 13744 KB Output is correct
60 Correct 45 ms 16828 KB Output is correct
61 Correct 68 ms 16024 KB Output is correct
62 Correct 266 ms 65956 KB Output is correct
63 Runtime error 417 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
64 Halted 0 ms 0 KB -