-
Notifications
You must be signed in to change notification settings - Fork 0
/
12. Collecting Numbers II.cpp
80 lines (73 loc) · 2.24 KB
/
12. Collecting Numbers II.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include "iostream"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef set<ll> sl;
typedef map<char, ll> mcl;
typedef map<ll, ll> mll;
typedef pair<char, ll> pcl;
typedef pair<ll, ll> pll;
#define PB push_back
#define F first
#define S second
#define I iterator
#define REP(i,a,b) for (ll i = a; i < b; i++)
#define REPR(i,a,b) for (ll i = a; i > b; i--)
#define REPJ(i,a,b,j) for (ll i = a; i < b; i+=j)
#define REPIT(it,o) for (auto it = o.begin(); it != o.end(); it++)
#define REPITR(it,o) for (auto it = o.rbegin(); it != o.rend(); it++)
int main() {
ll n=5,m=3;
// cin >> n >> m;
sl a;
vl v{4,2,1,5,3};
vl vr{-1,2,1,4,0,3};
ll ans = 1;
REP(i,0,n){
ll tmp=v[i];
// cin >> tmp;
if (a.count(tmp+1)){
ans++;
}
vr[tmp] = i;
// v[i]=tmp;
a.insert(tmp);
}
vector<pll> ms{make_pair(2,3), make_pair(1,5), make_pair(2,3)};
REP(i,0,m){
ll a=ms[i].F,b=ms[i].S;
// cin >> a >> b;
ll eaa = v[a-1];
ll tans = ans;
if (vr[eaa] < vr[eaa+1] && b-1 > vr[eaa+1]) tans++;
if (vr[eaa] > vr[eaa+1] && b-1 < vr[eaa+1]) tans--;
if (vr[eaa] < vr[eaa-1] && b-1 > vr[eaa-1]) tans--;
if (vr[eaa] > vr[eaa-1] && b-1 < vr[eaa-1]) tans++;
ll eab = v[b-1];
if (vr[eab] < vr[eab+1] && b-1 > vr[eab+1]) tans++;
if (vr[eab] > vr[eab+1] && b-1 < vr[eab+1]) tans--;
if (vr[eab] < vr[eab-1] && b-1 > vr[eab-1]) tans--;
if (vr[eab] > vr[eab-1] && b-1 < vr[eab-1]) tans++;
if (abs(eaa-eab) == 1){
if (tans > ans){
ans = tans-1;
} else if (tans < ans){
ans = tans+1;
} else {
ans = tans;
}
} else {
ans = tans;
}
v[a-1] = eab; v[b-1] = eaa;
vr[eaa] = b-1; vr[eab] = a-1;
cout << ans << ' ';
}
}
// TODO - incomplete
// - first approach
// loop over the array, for x, if x+1 is before the ele, increase the rounds. then loop over the changes check if it switched the occurence of a,a-1;a,a+1;b,b-1;b,b+1 adjust accordingly
// couldnt implement