oj.uz

Submission #117344

# Submission time Handle Problem Language Result Execution time Memory
117344 2019-06-15T14:14:08 Z JohnTitor Highway design (CEOI12_highway) C++11
60 / 100
 6 ms 1404 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "Highway"
#ifdef Aria
    void Answer(int a, int b, int c, int d){}
    bool isOnLine(int a, int b, int c){}
    int GetN(){};
#else
#include "office.h"
#endif // Aria
int n;
int a=1;
int x, y, z, t;
void answer(int a, int b, int c, int d){
//    assert(a);
//    assert(b);
//    assert(c);
//    assert(d);
//    assert(a!=b);
//    assert(a!=c);
//    assert(a!=d);
//    assert(b!=c);
//    assert(b!=d);
//    assert(c!=d);
    Answer(a, b, c, d);
    exit(0);
}
bool isonline(int a, int b, int c){
//    assert(a);
//    assert(b);
//    assert(c);
//    assert(a!=b);
//    assert(a!=c);
//    assert(b!=c);
    return isOnLine(a, b, c);
}
vector <int> all;
int main(){
    n=GetN();
    FOR(i, 1, n) all.pb(i);
    shuffle(all.begin(), all.end(), rng);
    a=all.back();
    all.pop_back();
//    bool bad=1;
    while(true){
        int b=all.back();
        all.pop_back();
        int c=all.back();
        all.pop_back();
        if(isonline(a, b, c)){
            t=b;
            continue;
        }
        else{
//            assert(all.size());
            int d=all.back();
            all.pop_back();
            if(isonline(a, b, d)){
                x=a;
                y=b;
                z=c;
            }
            else if(isonline(a, c, d)){
                x=a;
                y=c;
                z=b;
            }
            else{
                x=b;
                y=c;
                z=a;
                if(t) answer(x, y, z, t);
                all.pb(d);
            }
//            bad=0;
            break;
        }
    }
//    if(bad) assert(0);
    while(true){
//        assert(all.size());
        int p=all.back();
        all.pop_back();
//        assert(all.size());
        int q=all.back();
        all.pop_back();
        if(isonline(x, p, q)) continue;
        if(isonline(x, y, p)) t=q;
        else t=p;
        break;
    }
//    answer(x, y, z, t);
}

Compilation message

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);
     ~~~~~^~~~~~~~~~~

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct - 21 queries, 4 points
2 Correct 2 ms 256 KB Output is correct - 11 queries, 4 points
3 Correct 2 ms 256 KB Output is correct - 157 queries, 4 points
4 Incorrect 2 ms 384 KB Output isn't correct - Wrong answer
5 Correct 2 ms 384 KB Output is correct - 252 queries, 4 points
6 Incorrect 2 ms 384 KB Output isn't correct - Wrong answer
7 Correct 2 ms 384 KB Output is correct - 351 queries, 4 points
8 Correct 2 ms 384 KB Output is correct - 401 queries, 4 points
9 Correct 2 ms 384 KB Output is correct - 451 queries, 4 points
10 Incorrect 2 ms 384 KB Output isn't correct - Wrong answer
11 Correct 2 ms 384 KB Output is correct - 1002 queries, 4 points
12 Incorrect 3 ms 384 KB Output isn't correct - Wrong answer
13 Correct 2 ms 384 KB Output is correct - 1503 queries, 4 points
14 Incorrect 2 ms 384 KB Output isn't correct - Wrong answer
15 Correct 3 ms 384 KB Output is correct - 2504 queries, 4 points
16 Incorrect 2 ms 384 KB Output isn't correct - Wrong answer
17 Correct 2 ms 384 KB Output is correct - 855 queries, 4 points
18 Correct 2 ms 384 KB Output is correct - 901 queries, 4 points
19 Incorrect 3 ms 640 KB Output isn't correct - Wrong answer
20 Correct 3 ms 768 KB Output is correct - 15001 queries, 4 points
21 Incorrect 4 ms 896 KB Output isn't correct - Wrong answer
22 Incorrect 4 ms 896 KB Output isn't correct - Wrong answer
23 Incorrect 5 ms 1276 KB Output isn't correct - Wrong answer
24 Correct 6 ms 1276 KB Output is correct - 40945 queries, 4 points
25 Correct 6 ms 1404 KB Output is correct - 50000 queries, 4 points