제출 #380399

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
380399		LittlePants	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	0 / 100	2 ms	1004 KiB

skyscraper

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define pb push_back
#define sz(x) (int)(x.size())
#define all(x) x.begin(), x.end()
#define int long long
#define pii pair<int, int>
#define inf 1e9
#define mod 1000000007
#define F first
#define S second
#define wopen(x) freopen((x),"w",stdout)
#define ropen(x) freopen((x),"r",stdin)
#define de(x) cout << #x << " = " << x << ' '
#define IO ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
 
const int mxN = 3e4 + 5;
int n, m, b[mxN], p[mxN];
bitset<mxN * mxN> vis;
bitset<mxN> used;
vector<int> v[mxN];

namespace io {
    const int SIZE = 1e7 + 10;
    char inbuff[SIZE];
    char *l, *r;
    inline void init() {
        l = inbuff;
        r = inbuff + fread(inbuff, 1, SIZE, stdin);
    }
    inline char gc() {
        if (l == r) init();
        return (l != r) ? *(l++) : EOF;
    }
    void read(int &x) {
        x = 0; char ch = gc();
        while(!isdigit(ch)) ch = gc();
        while(isdigit(ch)) x = x * 10 + ch - '0', ch = gc();
    }
} using io::read;
 
signed main() {
	IO;
	cin >> n >> m;
	for(int i = 0; i < m; i++) cin >> b[i] >> p[i], v[b[i]].pb(p[i]);
	int ok = 0;
	for(int i = 0; i < m; i++) {
		if(i == 1) continue;
		int t = abs(b[i] - 1);
		if(t % p[i] == 0) {
			ok = 1;
			break;
		}
	}
	if(!ok) {
		cout << -1 << '\n';
		return 0;
	}
	queue<array<int, 3>> q;
	q.push({b[0], p[0], 0});
	while(!q.empty()) {
		auto now = q.front(); q.pop();
		vis[now[0] * n + now[1]] = 1;
		if(now[0] == b[1]) {
			cout << now[2] << '\n';
			return 0;
		}
		if(!used[now[0]]) {
			for(int i : v[now[0]]) {
				if(now[0] + i < n and vis[(now[0] + i) * n + i] == 0) 
					q.push({now[0] + i, i, now[2] + 1});
				if(now[0] - i >= 0 and vis[(now[0] - i) * n + i] == 0) 
					q.push({now[0] - i, i, now[2] + 1});
			}
		}
		used[now[0]] = 1;
		if(now[0] + now[1] < n and vis[(now[0] + now[1]) * n + now[1]] == 0) 
				q.push({now[0] + now[1], now[1], now[2] + 1});
		if(now[0] - now[1] >= 0 and vis[(now[0] - now[1]) * n + now[1]] == 0)
				q.push({now[0] - now[1], now[1], now[2] + 1});
	}
	cout << -1 << '\n';
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43