oj.uz

답안 #26743

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26743 2017-07-05T11:03:56 Z model_code Sticks (POI11_pat) C++14
100 / 100
 349 ms 13548 KB 
/*************************************************************************
 *                                                                       *
 *                    XVIII Olimpiada Informatyczna                      *
 *                                                                       *
 *   Zadanie:           Patyczki                                         *
 *   Autor:             Miroslaw Michalski                               *
 *   Zlozonosc czasowa: O(n * lg(n))                                     *
 *   Opis:              Rozwiazanie weryfikujace                         *
 *                                                                       *
 *************************************************************************/

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

inline bool triangle(const int a, const int b, const int c) {
    return (a + b > c && a + c > b && b + c > a);
}

inline bool diff(const int a, const int b, const int c) {
    return (a != b && a != c && b != c);
}

size_t n;

// zwraca element z pozycji >= pos tze jego kolor jest rowny 
// kolorowi pos
size_t analBlock(const vector<pair<int, int> >& v, size_t pos) {
    int currColor = v[pos].second;
    while (pos + 1 < n && v[pos + 1].second == currColor) {
        pos++;
    }
    return pos;
}

int main() {
    int k, il, x;
    vector<pair<int, int> > v;

    scanf("%d", &k);
    for(int c = 1; c <= k; c++) {
        scanf("%d", &il);
        for(int i = 0; i < il; i++) {
            scanf("%d", &x);
            v.push_back(make_pair(x, c));
        }
    }
    sort(v.begin(), v.end());
    n = v.size();
    v.push_back(make_pair(-1, -1));

    bool done = false;
    size_t pos = 0;
    while (!done) {
        size_t p1 = analBlock(v, pos);
        size_t p2 = analBlock(v, p1 + 1);
        size_t p3 = p2 + 1;
        pos = p2;
        if (p1 < n && p2 < n && p3 < n) {
            if (triangle(v[p1].first, v[p2].first, v[p3].first) && 
                    diff(v[p1].second, v[p2].second, v[p3].second)) {
                printf("%d %d %d %d %d %d\n", v[p1].second, v[p1].first, 
                        v[p2].second, v[p2].first, v[p3].second, v[p3].first);
                return 0;
            }
        } else {
            done = true;
        }
    }
    printf("NIE\n");
    return 0;
}

Compilation message

pat.cpp: In function 'int main()':
pat.cpp:42:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
                    ^
pat.cpp:44:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &il);
                         ^
pat.cpp:46:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
                            ^

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1176 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1176 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1176 KB Output is correct

Subtask #4
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1176 KB Output is correct
2 Correct 0 ms 1176 KB Oczekiwano NIE

Subtask #5
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1176 KB Oczekiwano NIE
2 Correct 6 ms 1644 KB Output is correct

Subtask #6
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1176 KB Oczekiwano NIE
2 Correct 9 ms 2028 KB Output is correct

Subtask #7
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1316 KB Oczekiwano NIE
2 Correct 26 ms 2796 KB Output is correct

Subtask #8
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1644 KB Oczekiwano NIE
2 Correct 43 ms 4332 KB Output is correct
3 Correct 26 ms 2796 KB Oczekiwano NIE

Subtask #9
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 2796 KB Oczekiwano NIE
2 Correct 59 ms 7404 KB Output is correct
3 Correct 43 ms 4332 KB Oczekiwano NIE

Subtask #10
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 143 ms 7404 KB Output is correct
2 Correct 89 ms 7404 KB Output is correct
3 Correct 69 ms 4332 KB Oczekiwano NIE

Subtask #11
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 7404 KB Output is correct
2 Correct 99 ms 7404 KB Output is correct
3 Correct 83 ms 7404 KB Oczekiwano NIE

Subtask #12
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 349 ms 13548 KB Output is correct
2 Correct 116 ms 7404 KB Output is correct
3 Correct 169 ms 7404 KB Oczekiwano NIE

Subtask #13
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 319 ms 13548 KB Output is correct
2 Correct 123 ms 7404 KB Output is correct
3 Correct 159 ms 13548 KB Oczekiwano NIE