| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 78441 | Saboon | Triangles (CEOI18_tri) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <queue>
#include <bitset>
#include <stack>
#include <vector>
#include <trilib.h>
#include <cstring>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <algorithm>
#include <iomanip>
#define prime first
#define alpha second
#define PB push_back
#define PF push_front
#define MP make_pair
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef unsigned long long ull;
const int maxn = 1e5 + 100;
int first = 1;
/*
int get_n () {
int k;
cin >> k;
return k;
}
bool is_clockwise (int fi, int se, int th) {
cout << fi << " " << se << " " << th << endl;
bool k;
cin >> k;
return k;
}
void give_answer (int x) {
cout << x << endl;
}
*/
int pre[maxn], nex[maxn];
void remove (int fi, int mid, int se) {
pre[se] = fi;
nex[fi] = se;
first = fi;
}
void insert (int fi, int mid, int se) {
nex[fi] = mid;
nex[mid] = se;
pre[se] = mid;
pre[mid] = fi;
}
int main() {
ios::sync_with_stdio(false);
int n = get_n ();
for (int i = 1; i <= n; i++)
a[i] = i;
random_shulfe (a + 1, a + n + 1);
if (is_clockwise (a[1], a[2], a[3])) {
nex[a[1]] = a[2];
nex[a[2]] = a[3];
nex[a[3]] = a[1];
pre[a[1]] = a[3];
pre[a[2]] = a[1];
pre[a[3]] = a[2];
}
else {
nex[a[1]] = a[3];
nex[a[3]] = a[2];
nex[a[2]] = a[1];
pre[a[1]] = a[2];
pre[a[2]] = a[3];
pre[a[3]] = a[1];
}
first = a[1];
for (int i = 4; i <= n; i++) {
int st = first, found = 0;
while (true) {
if (!is_clockwise (st, nex[st], a[i])) {
insert (st, a[i], nex[st]);
found = 1;
break;
}
st = nex[st];
if (st == first)
break;
}
if (!found)
continue;
while (!is_clockwise (a[i], nex[a[i]], nex[nex[a[i]]]))
remove (a[i], nex[a[i]], nex[nex[a[i]]]);
while (!is_clockwise (pre[pre[a[i]]], pre[a[i]], a[i]))
remove (pre[pre[a[i]]], pre[a[i]], a[i]);
}
int cnt = 0, st = first;
while (true) {
cnt ++;
st = nex[st];
if (st == first)
break;
}
give_answer (cnt);
}