답안 #1015132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1015132	2024-07-06T06:33:18 Z	deera	늑대인간 (IOI18_werewolf)	C++14	컴파일 오류	0 ms	0 KB

werewolf

#include <bits/stdc++.h>
using namespace std;

deque<int> line;
int NUM;
map<int, vector<int>> roads;

vector<int> minT;
vector<int> maxT;

void build_minT(int n) {
    if (n >= NUM) {
        minT[n] = line[n - NUM];
        return;
    } else {
        build_minT(2 * n);
        build_minT(2 * n + 1);
        minT[n] = min(minT[2 * n], minT[2 * n + 1]);
    }
}

int query_minT(int a, int b) {
    if (a == b) return minT[a + NUM];
    if (a > b) return INT_MAX;

    a += NUM;
    b += NUM;
    int res = INT_MAX;
    while (a <= b) {
        if (a % 2 == 1) {
            res = min(res, minT[a]);
            a++;
        }
        if (b % 2 == 0) {
            res = min(res, minT[b]);
            b--;
        }
        a /= 2;
        b /= 2;
    }
    return res;
}

void build_maxT(int n) {
    if (n >= NUM) {
        maxT[n] = line[n - NUM];
        return;
    } else {
        build_maxT(2 * n);
        build_maxT(2 * n + 1);
        maxT[n] = max(maxT[2 * n], maxT[2 * n + 1]);
    }
}

int query_maxT(int a, int b) {
    if (a == b) return maxT[a + NUM];
    if (a > b) return INT_MIN;

    a += NUM;
    b += NUM;
    int res = INT_MIN;
    while (a <= b) {
        if (a % 2 == 1) {
            res = max(res, maxT[a]);
            a++;
        }
        if (b % 2 == 0) {
            res = max(res, maxT[b]);
            b--;
        }
        a /= 2;
        b /= 2;
    }
    return res;
}

void make_line(bool x) {
    if (x == true) {
        int last = line.back();
        vector<int> a = roads[last];

        if (a.size() == 1) {
            if (a[0] != line[line.size() - 2]) {
                line.push_back(a[0]);
            }
            make_line(false);
        } else {
            if (a[0] == line[line.size() - 2]) {
                line.push_back(a[1]);
                make_line(true);
            } else {
                line.push_back(a[0]);
                make_line(true);
            }
        }
    } else {
        int last = line.front();
        vector<int> a = roads[last];

        if (a.size() == 1) {
            line.push_front(a[0]);
            return;
        } else {
            if (a[0] == line[1]) {
                line.push_back(a[1]);
                make_line(false);
            } else {
                line.push_back(a[0]);
                make_line(false);
            }
        }
    }
}

int[] check_validity(int N, int[] X, int[] Y, int[] S, int[] E, int[] L, int[] R) {
    NUM = N;

    for(int i=1;i<=N;i++) {
        vector<int> a;
        roads[i] = a;
    }

    for(int i=0;i<X.size();i++) {
        roads[X[i]].push_back(Y[i]);
        roads[Y[i]].push_back(X[i]);
    }

    for (auto i: roads) {
        if (i.second.size() == 1) {
            line.push_back(i.first);
            line.push_back(i.second[0]);
            break;
        }
    }

    while (true) {
        vector<int> next = roads[line.back()];
        if (next.size() == 1) {
            break;
        } else {
            if (next[0] == line[line.size() - 2]) {
                line.push_back(next[1]);
            } else {
                line.push_back(next[0]);
            }
        }
    }


    minT.resize(2 * NUM);
    maxT.resize(2 * NUM);

    build_minT(1);
    build_maxT(1);

    vector<int> ans;

    for(int q=0;q<S.size();q++) {
        int s = S[q];
        int e = E[q];
        int l = L[q];
        int r = R[q];

        int mid = (s + e) / 2;
        while (true) {
            if (s >= e) {
                ans.push_back(1);
                break;
            }

            int minR = query_minT(s, mid);
            int maxR = query_maxT(mid + 1, e);

            if (minR <= l && maxR >= r) {
                ans.push_back(0);
            } else if (minR <= l) {
                e = mid;
                mid = (s + e) / 2;
            } else if (maxR >= r) {
                s = mid + 1;
                mid = (s + e) / 2;
            } else {
                ans.push_back(1);
                break;
            }
        }
    }

    return ans;
}

Compilation message

werewolf.cpp:115:4: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  115 | int[] check_validity(int N, int[] X, int[] Y, int[] S, int[] E, int[] L, int[] R) {
      |    ^
werewolf.cpp:115:4: error: structured binding declaration cannot have type 'int'
  115 | int[] check_validity(int N, int[] X, int[] Y, int[] S, int[] E, int[] L, int[] R) {
      |    ^~
werewolf.cpp:115:4: note: type must be cv-qualified 'auto' or reference to cv-qualified 'auto'
werewolf.cpp:115:4: error: empty structured binding declaration
werewolf.cpp:115:7: error: expected initializer before 'check_validity'
  115 | int[] check_validity(int N, int[] X, int[] Y, int[] S, int[] E, int[] L, int[] R) {
      |       ^~~~~~~~~~~~~~