oj.uz

답안 #307872

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
307872 2020-09-29T12:51:51 Z Vimmer 버섯 세기 (IOI20_mushrooms) C++14
0 / 100
 211 ms 1772 KB 
#include <bits/stdc++.h>
#include "mushrooms.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define N 100005
#define PB push_back
#define sz(x) int(x.size())
#define F first
#define M ll(1e9 + 7)
#define S second
#define all(x) x.begin(), x.end()
#define endl '\n'

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
//typedef tree <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int ask(vector <int> &m) { return use_machine(m);}
int ask(set <int> &se) {vector <int> m; m.clear(); for (auto it : se) m.PB(it); return use_machine(m);}

ll mlt(ll x, ll y) {return (x * y) % M;}
ll sm(ll x, ll y) {return (x + y) % M;}

int NEED = 2, nr;

vector <int> tr;

int es_minus_3(vector <int> &pr, set <int> &se)
{
    int ans = sz(pr);

    while (sz(se) > 0)
    {
        int i = 0;

        vector <int> m; m.clear();

        while (i + 1 < sz(pr) && sz(se) > 0)
        {
            m.PB(pr[i++]);

            m.PB(*se.begin());

            se.erase(se.begin());
        }

        m.PB(pr[i]);

        ans += (sz(m) / 2) - (ask(m) / 2);
    }

    return ans;
}

void fnd(set <int> &se)
{
    if (sz(se) == 2)
    {
       vector <int> m; m.clear(); m.PB(0); m.PB(*se.begin());

       if (ask(m) == 0)
       {
            tr.PB(*se.begin());

            se.erase(se.begin());
       }
       else
       {
            tr.PB(*se.rbegin());

            se.erase(*se.rbegin());
       }

       return;
    }

    if (sz(se) == 3)
    {
        vector <int> m; m.clear(); m.PB(*se.begin()); se.erase(se.begin()); m.PB(*se.begin()); se.erase(se.begin());

        if (ask(m) == 0)
        {
            vector <int> pl; pl.clear();

            pl.PB(0); pl.PB(*se.begin());

            if (ask(pl) == 0) {tr.PB(*se.begin()); se.erase(*se.begin()); se.insert(m[0]); se.insert(m[1]); return;}
              else {tr.PB(m[0]); tr.PB(m[1]); return;}
        }

        set <int> st; st.clear();

        st.insert(m[0]); st.insert(m[1]);

        fnd(st);

        for (auto it : st) se.insert(it);

        return;
    }

    set <int> st; st.clear();

    int nm = sz(se) / 2;

    while (sz(st) < nm) {st.insert(*se.begin()); se.erase(se.begin());}

    if (ask(st) != 0) fnd(st);
      else if (ask(se) != 0) fnd(se);
        else
        {
            int l = *st.rbegin(), r = *se.begin();

            vector <int> m = {l, 0};

            if (ask(m) == 0) st.erase(l);
              else se.erase(r);
        }

    for (auto it : st) se.insert(it);
}

int count_mushrooms(int n)
{
    nr = n;

    tr.PB(0);

    vector <int> m; m.clear();

    m.PB(0);

    set <int> se; se.clear();

    for (int i = 1; i < n; i++) se.insert(i);

    int i = 1;

    while (i < n && sz(tr) < NEED)
    {
        m.PB(i);

        int val = ask(m);

        m.pop_back();

        if (val == 1) break;

        se.erase(i);

        tr.PB(i++);
    }

    while (sz(tr) < NEED && sz(se) > 0)
    {
        if (sz(se) == 1)
        {
            vector <int> m = {0, *se.begin()};

            if (ask(m) == 0) tr.PB(*se.begin());

            return sz(tr);
        }

        if (ask(se) == 0) return sz(tr);

        fnd(se);
    }

    return es_minus_3(tr, se);
}

//int main()
//{
//    iostream::sync_with_stdio(0); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//
//    //freopen("fcolor.in", "r", stdin); freopen("fcolor.out", "w", stdout);
//
//
//}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Partially correct 22 ms 508 KB Output is partially correct
7 Partially correct 188 ms 1280 KB Output is partially correct
8 Partially correct 196 ms 1280 KB Output is partially correct
9 Partially correct 211 ms 1280 KB Output is partially correct
10 Partially correct 166 ms 1280 KB Output is partially correct
11 Partially correct 184 ms 1280 KB Output is partially correct
12 Partially correct 171 ms 1280 KB Output is partially correct
13 Incorrect 197 ms 1772 KB Too many queries.
14 Halted 0 ms 0 KB -