Submission #1319471
Source Code Expand
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
int a[100010], b[100010];
int dp[2][100010];
bool used[100010];
signed main(void)
{
int n, q;
cin >> n >> q;
REP(i, q) {
cin >> a[i] >> b[i];
a[i]--, b[i]--;
}
VI v[2];
int cur = 0, vis = 1;
dp[0][0] = 1;
dp[0][1] = 2;
v[0].PB(0); v[0].PB(1);
//REP(i, n) cout << dp[cur][i] << " "; cout << endl;
REP(i, q) {
memset(used, false, sizeof(used));
for(int j: v[cur]) {
//cout << "j:" << j << endl;
if(used[j]) continue;
used[j] = true;
if(a[i] == j) {
dp[vis][b[i]] = dp[cur][j];
v[vis].PB(b[i]);
if(dp[cur][j] == 1) {
if(b[i] != 0 && dp[vis][b[i]-1] == 0) {
/*cout << "b-1:" << b[i]-1 << endl;*/ dp[vis][b[i]-1] = 2; v[vis].PB(b[i]-1);
}
if(b[i] != n-1 && dp[vis][b[i]+1] == 0) {
/*cout << "b+1:" << b[i]+1 << endl;*/ dp[vis][b[i]+1] = 2; v[vis].PB(b[i]+1);
}
}
} else if(b[i] == j) {
dp[vis][a[i]] = dp[cur][j];
v[vis].PB(a[i]);
if(dp[cur][j] == 1) {
if(a[i] != 0 && dp[vis][a[i]-1] == 0) {
/*cout<<"a-1:"<<a[i]-1;*/ dp[vis][a[i]-1] = 2; v[vis].PB(a[i]-1);
}
if(a[i] != n-1 && dp[vis][a[i]+1] == 0) {
/*cout<<"a+1:"<<a[i]+1;*/ dp[vis][a[i]+1] = 2; v[vis].PB(a[i]+1);
}
}
} else {
dp[vis][j] = dp[cur][j];
v[vis].PB(j);
if(dp[cur][j] == 1) {
if(j != 0 && dp[vis][j-1] == 0) {
/*cout << "j-1:" << j-1 << endl;*/ dp[vis][j-1] = 2; v[vis].PB(j-1);
}
if(j != n-1 && dp[vis][j+1] == 0) {
/*cout << "j+1:" << j+1 << endl;*/ dp[vis][j+1] = 2; v[vis].PB(j+1);
}
}
}
dp[cur][j] = 0;
}
v[cur].erase(ALL(v[cur]));
//REP(j, n) cout << dp[vis][j] << " "; cout << endl;
cur ^= 1;
vis ^= 1;
}
ll ret = 0;
REP(i, n) if(dp[cur][i] != 0) {
ret++;
//cout << i << " ";
}
cout << ret << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
G - Magician |
User |
ferin_tech |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2493 Byte |
Status |
AC |
Exec Time |
380 ms |
Memory |
1280 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt |
All |
sample_01.txt, sample_02.txt, sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
384 KB |
sample_02.txt |
AC |
1 ms |
384 KB |
subtask1_01.txt |
AC |
378 ms |
1152 KB |
subtask1_02.txt |
AC |
377 ms |
1152 KB |
subtask1_03.txt |
AC |
376 ms |
1152 KB |
subtask1_04.txt |
AC |
376 ms |
1152 KB |
subtask1_05.txt |
AC |
377 ms |
1152 KB |
subtask1_06.txt |
AC |
377 ms |
1152 KB |
subtask1_07.txt |
AC |
380 ms |
1280 KB |
subtask1_08.txt |
AC |
378 ms |
1152 KB |
subtask1_09.txt |
AC |
380 ms |
1152 KB |
subtask1_10.txt |
AC |
375 ms |
1152 KB |
subtask1_11.txt |
AC |
380 ms |
1280 KB |
subtask1_12.txt |
AC |
376 ms |
1152 KB |
subtask1_13.txt |
AC |
380 ms |
1280 KB |
subtask1_14.txt |
AC |
379 ms |
1152 KB |
subtask1_15.txt |
AC |
376 ms |
1280 KB |
subtask1_16.txt |
AC |
377 ms |
1152 KB |
subtask1_17.txt |
AC |
377 ms |
1152 KB |
subtask1_18.txt |
AC |
377 ms |
1152 KB |
subtask1_19.txt |
AC |
378 ms |
1152 KB |