#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
highway.cpp: In function 'int main()':
highway.cpp:123:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < pot.size(); i++)
~~^~~~~~~~~~~~
highway.cpp:124:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i == pot.size() - 1 && t2.empty())
~~^~~~~~~~~~~~~~~~~
highway.cpp:122:9: warning: unused variable 'fl' [-Wunused-variable]
int fl = 0;
^~
office.c: In function 'int isOnLine(int, int, int)':
office.c:85:29: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
_Fin(0, "Protocol error");
^
office.c:88:29: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
_Fin(0, "Protocol error");
^
office.c:92:37: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
_Fin(false, "Too many questions");
^
office.c:83:7: warning: unused variable 'i' [-Wunused-variable]
int i;
^
office.c: In function 'void Answer(int, int, int, int)':
office.c:123:29: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
_Fin(0, "Protocol error");
^
office.c:128:44: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if( (-_Apa[na1]==_N-3) && (na2!=na1) && (nb2!=na1) ||
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
office.c:130:30: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
_Fin(true, "Correct");
^
office.c:132:36: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
_Fin(false, "Wrong answer");
^
office.c:134:44: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if( (-_Apa[na2]==_N-3) && (na1!=na2) && (nb1!=na2) ||
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
office.c:136:30: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
_Fin(true, "Correct");
^
office.c:138:36: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
_Fin(false, "Wrong answer");
^
office.c:140:33: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
_Fin(false, "Wrong answer");
^
office.c:142:23: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
_Fin(true, "Correct");
^
office.c:120:27: warning: unused variable 'pont' [-Wunused-variable]
int na1, nb1, na2, nb2, pont;
^~~~
office.c: In function 'void _doInit()':
office.c:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &_N);
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
388 KB |
Output is correct - 20 queries, 4 points |
| 2 |
Correct |
3 ms |
388 KB |
Output is correct - 9 queries, 4 points |
| 3 |
Correct |
3 ms |
480 KB |
Output is correct - 156 queries, 4 points |
| 4 |
Correct |
3 ms |
612 KB |
Output is correct - 200 queries, 4 points |
| 5 |
Correct |
3 ms |
716 KB |
Output is correct - 251 queries, 4 points |
| 6 |
Correct |
3 ms |
716 KB |
Output is correct - 302 queries, 4 points |
| 7 |
Correct |
3 ms |
716 KB |
Output is correct - 350 queries, 4 points |
| 8 |
Correct |
3 ms |
752 KB |
Output is correct - 399 queries, 4 points |
| 9 |
Correct |
2 ms |
752 KB |
Output is correct - 450 queries, 4 points |
| 10 |
Correct |
1 ms |
752 KB |
Output is correct - 500 queries, 4 points |
| 11 |
Correct |
3 ms |
752 KB |
Output is correct - 1001 queries, 4 points |
| 12 |
Correct |
3 ms |
752 KB |
Output is correct - 1001 queries, 4 points |
| 13 |
Correct |
3 ms |
760 KB |
Output is correct - 1502 queries, 4 points |
| 14 |
Correct |
3 ms |
852 KB |
Output is correct - 2003 queries, 4 points |
| 15 |
Correct |
3 ms |
852 KB |
Output is correct - 2502 queries, 4 points |
| 16 |
Correct |
4 ms |
852 KB |
Output is correct - 803 queries, 4 points |
| 17 |
Correct |
3 ms |
908 KB |
Output is correct - 854 queries, 4 points |
| 18 |
Correct |
3 ms |
908 KB |
Output is correct - 900 queries, 4 points |
| 19 |
Correct |
4 ms |
1316 KB |
Output is correct - 12705 queries, 4 points |
| 20 |
Correct |
5 ms |
1448 KB |
Output is correct - 15000 queries, 4 points |
| 21 |
Correct |
6 ms |
1712 KB |
Output is correct - 20060 queries, 4 points |
| 22 |
Correct |
6 ms |
1968 KB |
Output is correct - 28061 queries, 4 points |
| 23 |
Correct |
4 ms |
2228 KB |
Output is correct - 33888 queries, 4 points |
| 24 |
Correct |
13 ms |
2576 KB |
Output is correct - 40944 queries, 4 points |
| 25 |
Correct |
17 ms |
3040 KB |
Output is correct - 49998 queries, 4 points |
