oj.uz

Submission #43752

# Submission time Handle Problem Language Result Execution time Memory
43752 2018-03-22T10:35:58 Z chpipis Carnival (CEOI14_carnival) C++11
100 / 100
 36 ms 2296 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)

// START for segment tree
#define params int p, int L, int R
#define housekeep int mid = (L + R) >> 1, left = p << 1, right = left | 1
// END

#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
    advance(it, -n);
    return it;
}

template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
    advance(it, n);
    return it;
}
#endif

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

template<typename T>
inline T sq(T a) { return a * a; }

//#ifdef LOCAL_MACHINE
//#endif

map<vi, int> memo;

int query(vi vec) {
    if (vec.size() <= 1) return (int)vec.size();
    sort(all(vec));
    if (memo.count(vec)) return memo[vec];
    printf("%d", (int)vec.size());
    for (auto it : vec) printf(" %d", it);
    puts("");
    fflush(stdout);
    int res;
    scanf("%d", &res);
    return memo[vec] = res;
}

int solve(int l, int r, vi &vec) {
    if (l > r) return 0;
    if (l == r) {
        vec = {1};
        return 1;
    }

    int mid = (l + r) >> 1;

    vi left, right;
    int a = solve(l, mid, left);
    int b = solve(mid + 1, r, right);

    vector<bool> inside(r - l + 1, true);

    for (int i = l; i <= mid; i++) {
        if (inside[i - l]) {
            for (int j = i + 1; j <= mid; j++)
                if (left[i - l] == left[j - l])
                    inside[j - l] = false;
        }
    }

    for (int i = mid + 1; i <= r; i++) {
        if (inside[i - l]) {
            for (int j = i + 1; j <= r; j++)
                if (right[i - mid - 1] == right[j - mid - 1])
                    inside[j - l] = false;
        }
    }

    vi cur;
    for (int i = l; i <= r; i++)
        if (inside[i - l])
            cur.pb(i);
    int c = query(cur);

    vec.assign(r - l + 1, 0);
    int last = 0;

    int curc = c;
    for (int i = l; i <= r; i++) {
        if (!inside[i - l]) continue;
        cur.erase(find(all(cur), i));
        int now = query(cur);
        if (now < curc) {
            curc--;
            last++;
            if (i <= mid) {
                for (int j = l; j <= mid; j++)
                    if (left[j - l] == left[i - l])
                        vec[j - l] = last;
            } else {
                for (int j = mid + 1; j <= r; j++) {
                    if (right[j - mid - 1] == right[i - mid - 1])
                        vec[j - l] = last;
                }
            }
        } else {
            cur.pb(i);
        }
    }

    for (int i = l; i <= mid; i++) {
        if (vec[i - l] != 0) continue;
        last++;
        for (int j = l; j <= mid; j++)
            if (left[i - l] == left[j - l])
                vec[j - l] = last;
        int found = -1;
        for (int j = mid + 1; j <= r; j++) {
            if (vec[j - l] != 0) continue;
            cur = {i, j};
            if (query(cur) == 1) {
                found = j;
                break;
            }
        }
        if (found != -1) {
            for (int j = mid + 1; j <= r; j++)
                if (right[j - mid - 1] == right[found - mid - 1])
                    vec[j - l] = last;
        }
    }

    return c;
}

int main() {
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    int n;
    scanf("%d", &n);
    vi vec;
    solve(1, n, vec);
    printf("0");
    for (auto it : vec) printf(" %d", it);
    puts("");
    return 0;
}

Compilation message

carnival.cpp: In function 'int solve(int, int, vi&)':
carnival.cpp:82:9: warning: unused variable 'a' [-Wunused-variable]
     int a = solve(l, mid, left);
         ^
carnival.cpp:83:9: warning: unused variable 'b' [-Wunused-variable]
     int b = solve(mid + 1, r, right);
         ^
carnival.cpp: In function 'int query(vi)':
carnival.cpp:68:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &res);
                      ^
carnival.cpp: In function 'int main()':
carnival.cpp:164:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2164 KB Output is correct
2 Correct 1 ms 2164 KB Output is correct
3 Correct 11 ms 2164 KB Output is correct
4 Correct 3 ms 2164 KB Output is correct
5 Correct 3 ms 2032 KB Output is correct
6 Correct 3 ms 2032 KB Output is correct
7 Correct 5 ms 2164 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2164 KB Output is correct
2 Correct 36 ms 2296 KB Output is correct
3 Correct 5 ms 2164 KB Output is correct
4 Correct 7 ms 2164 KB Output is correct
5 Correct 3 ms 2164 KB Output is correct
6 Correct 2 ms 2032 KB Output is correct
7 Correct 4 ms 2164 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2032 KB Output is correct
2 Correct 14 ms 2164 KB Output is correct
3 Correct 9 ms 2296 KB Output is correct
4 Correct 4 ms 2164 KB Output is correct
5 Correct 5 ms 2164 KB Output is correct
6 Correct 5 ms 2164 KB Output is correct
7 Correct 6 ms 2164 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2164 KB Output is correct
2 Correct 2 ms 2164 KB Output is correct
3 Correct 15 ms 2164 KB Output is correct
4 Correct 9 ms 2164 KB Output is correct
5 Correct 5 ms 2164 KB Output is correct
6 Correct 7 ms 2164 KB Output is correct
7 Correct 4 ms 2164 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2164 KB Output is correct
2 Correct 11 ms 2164 KB Output is correct
3 Correct 10 ms 2164 KB Output is correct
4 Correct 4 ms 2164 KB Output is correct
5 Correct 2 ms 2164 KB Output is correct
6 Correct 4 ms 2164 KB Output is correct
7 Correct 10 ms 2164 KB Output is correct