oj.uz

답안 #531755

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
531755 2022-03-01T11:36:28 Z EqualTurtle 버섯 세기 (IOI20_mushrooms) C++14
100 / 100
 8 ms 328 KB 
#include<bits/stdc++.h>
#include "mushrooms.h"
#define notw (which+1)%2
#define zero1 sure[which][0]
#define zero2 sure[which][1]
#define zero3 sure[which][2]
#define zero4 sure[which][3]
#define one1 sure[notw][0]
#define A counter
#define B counter+1
#define C counter+2
#define D counter+3
#define E counter+4
using namespace std;

constexpr int maxk = 120;
vector <int> sure[2];
int res = 0;
int which, counter;

void assign(vector <int> v, int st)
{
    for (int i = 0; i < (int)v.size(); i++)
        sure[which ^ v[i]].push_back(st + i);
}

void quick_update()
{
    which = (sure[0].size() >= sure[1].size() ? 0 : 1);
    counter = sure[0].size() + sure[1].size();
}

void debug()
{
    for (int i : sure[0])
        cout << i << " ";
    cout << "\n";
    for (int i : sure[1])
        cout << i << " ";
    cout << "\n";

    cout << "-----------------\n";
}

void first_two()
{
    vector <int> arr = {0, 1};
    int curr = use_machine(arr);
    if (!curr){
        sure[0].push_back(1);
        return;
    }
    sure[1].push_back(1);
    arr = {0, 2};
    curr = use_machine(arr);

    if (curr == 0)
        sure[0].push_back(2);
    else
        sure[1].push_back(2);
}

void phase1_1(int k)
{
    quick_update();
    while (((int)sure[which].size() < 4 || (int)sure[notw].size() == 0) && ((int)sure[which].size() <= k)) // untill i have 4 zeros and 1 one
    {
        int curr = use_machine({zero1, A, B, C, D, E});

        if (curr == 0)
            assign({0, 0, 0, 0, 0}, A);
        else if (curr == 5)
            assign({1, 0, 1, 0, 1}, A);
        else if (curr == 1)
        {
            int curr2 = use_machine({0, B});
            if (curr2 == 1){
                curr2 = use_machine({0, A});
                assign({curr2, 1, 1, 1, 1}, A);
            }
            else{
                curr2 = use_machine({0, C, B, D});
                assign({0, 0, curr2 / 2, curr2 % 2, 1}, A);
            }
        }
        else if (curr == 3)
        {
            int curr2 = use_machine({0, D, C});
            if (curr2 % 2 == 0)
            {
                int curr3 = use_machine({0, A, C, B});
                assign({curr3 / 2, curr3 % 2, 0, curr2 / 2, 1}, A);
            }
            else
            {
                int curr3 = use_machine({E, A, C, B});
                assign({(curr3 / 2) == 0, (curr3 % 2) == 0, 1, curr3 == 1, 1}, A);
            }
        }
        else // curr % 2 == 0
        {
            int curr2 = use_machine({0, A, E, B});
            int curr3 = use_machine({0, C, E, D});
            assign({curr2 / 2, curr2 % 2, curr3 / 2, curr3 % 2, 0}, A);
        }

        quick_update();
    }
}

void phase1_2(int k)
{
    quick_update();
    while ((int)sure[which].size() <= k) // untill i have k zeros or ones
    {
        int curr = use_machine({A, zero1, B, zero2, C, D, one1, E});
        if (curr == 1){
            curr = use_machine({zero1, C, zero2, D});
            assign({0, 0, curr / 2, curr % 2, 1}, A);
        }
        else if (curr == 2){
            curr = use_machine({zero1, C, zero2, D, zero3, E});
            assign({curr % 2, 0, curr >= 4, curr >= 2, curr % 2}, A);
        }
        else if (curr == 3){
            curr = use_machine({C, zero1, B, zero2, E, zero3, D});

            if (curr == 3)
                assign({0, 0, 1, 0, 1}, A);
            else
                assign({curr < 3, curr > 3, (curr % 4) == 2, (curr % 4) != 0, curr > 3}, A);
        }
        else if (curr == 4){
            curr = use_machine({C, zero1, A, zero2, D, zero3, E, zero4});
            assign({curr / 4, (curr % 4) != 1, curr % 2, (curr % 4) / 2, curr / 4}, A);
        }
        else if (curr == 5){
            curr = use_machine({A, zero1, C, zero2, D, zero3, E, zero4, B});
            assign({curr != 5, curr != 3, (curr != 2 && curr != 4), (curr == 6 || curr == 4), curr == 5}, A);
        }
        else if (curr == 6){
            curr = use_machine({zero1, A});
            assign({curr, 1, 1, 0, curr}, A);
        }
        else // curr == 7
            assign({1, 1, 1, 0, 0}, A); 

        quick_update();
    }
}

void phase2(int n)
{
    quick_update();

    while (counter < n)
    {
        int siz = min(n - counter, (int)sure[which].size());
 
        vector <int> arr;
        for (int i = 0; i < siz; i++){
            arr.push_back(sure[which][i]);
            arr.push_back(counter + i);
        }
 
        int curr = use_machine(arr);
        
        sure[(which ^ (curr % 2))].push_back(counter + siz - 1);
        res += (which == 0 ? siz - curr / 2 - 1 : curr/2);
 
        //quick_update();
        which = (sure[0].size() >= sure[1].size() ? 0 : 1);
        counter += siz;
    }
    res += (int)sure[0].size();
}

int count_mushrooms(int n)
{
    // corner case
    if (n == 2){
        vector <int> arr = {0, 1};
        int curr = use_machine(arr);
        if (curr == 0)
            curr = 2;
        return curr;
    }
    
    sure[0].push_back(0);

    if (n < 20)
        first_two();
    else{
        phase1_1(min(n/2 - 5, maxk));
        phase1_2(min(n/2 - 5, maxk));
    }
    phase2(n);
    return res;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 1 ms 200 KB Output is correct
6 Correct 2 ms 200 KB Output is correct
7 Correct 5 ms 200 KB Output is correct
8 Correct 4 ms 296 KB Output is correct
9 Correct 5 ms 200 KB Output is correct
10 Correct 7 ms 200 KB Output is correct
11 Correct 6 ms 200 KB Output is correct
12 Correct 6 ms 200 KB Output is correct
13 Correct 6 ms 200 KB Output is correct
14 Correct 5 ms 200 KB Output is correct
15 Correct 6 ms 200 KB Output is correct
16 Correct 7 ms 328 KB Output is correct
17 Correct 3 ms 200 KB Output is correct
18 Correct 6 ms 292 KB Output is correct
19 Correct 6 ms 304 KB Output is correct
20 Correct 6 ms 200 KB Output is correct
21 Correct 5 ms 300 KB Output is correct
22 Correct 6 ms 200 KB Output is correct
23 Correct 5 ms 304 KB Output is correct
24 Correct 5 ms 200 KB Output is correct
25 Correct 7 ms 200 KB Output is correct
26 Correct 6 ms 304 KB Output is correct
27 Correct 7 ms 200 KB Output is correct
28 Correct 7 ms 200 KB Output is correct
29 Correct 6 ms 200 KB Output is correct
30 Correct 5 ms 200 KB Output is correct
31 Correct 8 ms 292 KB Output is correct
32 Correct 6 ms 200 KB Output is correct
33 Correct 6 ms 200 KB Output is correct
34 Correct 6 ms 200 KB Output is correct
35 Correct 6 ms 200 KB Output is correct
36 Correct 8 ms 200 KB Output is correct
37 Correct 6 ms 308 KB Output is correct
38 Correct 8 ms 200 KB Output is correct
39 Correct 5 ms 200 KB Output is correct
40 Correct 8 ms 296 KB Output is correct
41 Correct 7 ms 300 KB Output is correct
42 Correct 6 ms 200 KB Output is correct
43 Correct 6 ms 304 KB Output is correct
44 Correct 6 ms 200 KB Output is correct
45 Correct 7 ms 200 KB Output is correct
46 Correct 6 ms 200 KB Output is correct
47 Correct 5 ms 200 KB Output is correct
48 Correct 6 ms 300 KB Output is correct
49 Correct 6 ms 200 KB Output is correct
50 Correct 8 ms 300 KB Output is correct
51 Correct 6 ms 300 KB Output is correct
52 Correct 6 ms 308 KB Output is correct
53 Correct 6 ms 200 KB Output is correct
54 Correct 6 ms 292 KB Output is correct
55 Correct 6 ms 200 KB Output is correct
56 Correct 7 ms 200 KB Output is correct
57 Correct 6 ms 200 KB Output is correct
58 Correct 6 ms 200 KB Output is correct
59 Correct 7 ms 200 KB Output is correct
60 Correct 6 ms 200 KB Output is correct
61 Correct 6 ms 200 KB Output is correct
62 Correct 0 ms 200 KB Output is correct
63 Correct 0 ms 200 KB Output is correct
64 Correct 0 ms 200 KB Output is correct
65 Correct 1 ms 200 KB Output is correct
66 Correct 1 ms 200 KB Output is correct
67 Correct 0 ms 200 KB Output is correct
68 Correct 0 ms 200 KB Output is correct
69 Correct 0 ms 200 KB Output is correct
70 Correct 0 ms 200 KB Output is correct
71 Correct 0 ms 272 KB Output is correct
72 Correct 0 ms 200 KB Output is correct
73 Correct 0 ms 200 KB Output is correct
74 Correct 0 ms 200 KB Output is correct
75 Correct 0 ms 200 KB Output is correct
76 Correct 1 ms 200 KB Output is correct
77 Correct 0 ms 200 KB Output is correct
78 Correct 0 ms 200 KB Output is correct
79 Correct 1 ms 200 KB Output is correct
80 Correct 0 ms 200 KB Output is correct
81 Correct 0 ms 200 KB Output is correct
82 Correct 1 ms 200 KB Output is correct
83 Correct 0 ms 200 KB Output is correct
84 Correct 0 ms 200 KB Output is correct
85 Correct 1 ms 200 KB Output is correct
86 Correct 0 ms 200 KB Output is correct
87 Correct 1 ms 200 KB Output is correct
88 Correct 1 ms 200 KB Output is correct
89 Correct 1 ms 200 KB Output is correct
90 Correct 1 ms 200 KB Output is correct
91 Correct 0 ms 200 KB Output is correct