| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 62814 | eriksuenderhauf | Highway design (CEOI12_highway) | C++11 | 17 ms | 3040 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 <bits/stdc++.h>
#include "office.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e6 + 5;
const double eps = 1e-9;
deque<vi> cur;
void brute()
{
vi a, b;
for (int i = 1; i < 3; i++)
for (int j = i + 1; j <= 3; j++)
{
int o1 = isOnLine(i, j, 4);
int o2 = isOnLine(i, j, 5);
int o3 = isOnLine(i, j, 6);
if (o1 + o2 + o3 == 0)
continue;
a.pb(i), a.pb(j), b.pb(6 - i - j);
if (o1 == 0)
b.pb(4);
if (o2 == 0)
b.pb(5);
if (o3 == 0)
b.pb(6);
Answer(a[0], a[1], b[0], b[1]);
exit(0);
}
exit(0);
}
vi pot;
int main()
{
int n = GetN();
int o1 = isOnLine(1, 2, 3), o2 = isOnLine(4, 5, 6);
if (o1 == 0 && o2 == 0)
brute();
if (o1 == 0)
pot.pb(1), pot.pb(2), pot.pb(3);
else
cur.pb({1,2,3});
if (o2 == 0)
pot.pb(4), pot.pb(5), pot.pb(6);
else
cur.pb({4,5,6});
for (int i = 7; i + 2 <= n; i += 3)
{
o1 = isOnLine(i, i + 1, i + 2);
if (o1 == 0)
{
pot.pb(i), pot.pb(i + 1), pot.pb(i + 2);
if (pot.size() == 6)
{
vi t1 = cur.front();
vi t2;
for (int i = 0; i < 6; i++)
if (isOnLine(t1[0], t1[1], pot[i]) == 0)
t2.pb(pot[i]);
Answer(t1[0], t1[1], t2[0], t2[1]);
exit(0);
}
}
else
cur.pb({i,i+1,i+2});
}
while (cur.size() > 2)
{
vi t1 = cur.back(); cur.pop_back();
vi t2 = cur.back(); cur.pop_back();
vi t3 = cur.back(); cur.pop_back();
o1 = isOnLine(t1[0], t2[0], t3[0]);
if (o1 == 0)
{
if (isOnLine(t1[0], t1[1], t2[0]) == 1)
Answer(t1[0], t1[1], t3[0], t3[1]);
else
Answer(t1[0], t1[1], t2[0], t2[1]);
exit(0);
}
cur.push_front({t1[0], t2[0], t3[0]});
}
while (cur.size() > 1)
{
vi t1 = cur.back(); cur.pop_back();
vi t2 = cur.back(); cur.pop_back();
o1 = isOnLine(t1[0], t1[1], t2[0]);
if (o1 == 0)
{
Answer(t1[0], t1[1], t2[0], t2[1]);
exit(0);
}
cur.push_front({t1[0], t1[1], t2[0]});
}
// at most 5 points over
vi t1 = cur.back(), t2;
int fl = 0;
for (int i = 0; i < pot.size(); i++)
if (i == pot.size() - 1 && t2.empty())
t2.pb(pot[i]);
else if (t2.size() != 2 && isOnLine(t1[0], t1[1], pot[i]) == 0)
t2.pb(pot[i]);
if (t2.size() > 1)
Answer(t1[0], t1[1], t2[0], t2[1]);
for (int i = n - (n % 3) + 1; i <= n; i++)
{
if (i == n - 1 && t2.empty())
t2.pb(i);
else if (i == n && t2.size() == 1)
t2.pb(i);
else if (t2.size() != 2 && isOnLine(t1[0], t1[1], i) == 0)
t2.pb(pot[i]);
}
Answer(t1[0], t1[1], t2[0], t2[1]);
return 0;
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||