oj.uz

답안 #314673

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
314673 2020-10-20T18:34:44 Z neizod 버섯 세기 (IOI20_mushrooms) C++17
100 / 100
 9 ms 392 KB 
// WIP: REFACTORING

#include "mushrooms.h"
#include <bits/stdc++.h>

using namespace std;

//int use_machine(vector<int> x);


const int M = 100;


void partV1(int &i, vector<int> &A, vector<int> &B, int &count_A, int &count_B){
    while(count_A < 2 && count_B < 2){
        vector<int> x = { 0, i };
        //x.push_back(0);
        //x.push_back(i);
        int result = use_machine(x);
        if(result == 0){
            A.push_back(i);
            count_A++;
        }
        else{
            B.push_back(i);
            count_B++;
        }
        i++;
    }
}


void partV2(int &i, vector<int> &A, vector<int> &B, int &count_A, int &count_B){
    // TODO while condition
    while ((count_A < 3 || count_B < 2) && (count_A < 2 || count_B < 3) && count_A < M && count_B < M){
        bool swapped = false;
        if (count_A < count_B) {
            swapped = true;
            swap(A, B);
            swap(count_A, count_B);
        }
        vector<int> x = { i, A[0], i+1, A[1] };
        //x.push_back(i);
        //x.push_back(A[0]);
        //x.push_back(i+1);
        //x.push_back(A[1]);
        int result = use_machine(x);
        switch(result){
            case 0:
                A.push_back(i);
                A.push_back(i+1);
                count_A += 2;
                break;
            case 1:
                B.push_back(i);
                A.push_back(i+1);
                count_A++;
                count_B++;
                break;
            case 2:
                A.push_back(i);
                B.push_back(i+1);
                count_A++;
                count_B++;
                break;
            default:
                B.push_back(i);
                B.push_back(i+1);
                count_B += 2;
        }
        if (swapped) {
            swap(A, B);
            swap(count_A, count_B);
        }
        i += 2;
    }
}


void partV3(int &i, vector<int> &A, vector<int> &B, int &count_A, int &count_B){
    while(count_A < M && count_B < M){
        bool swapped = false;
        if(count_A < count_B){
            swapped = true;
            swap(A, B);
            swap(count_A, count_B);
        }
        vector<int> x = { i, A[0], i+1, A[1], i+2, A[2] };
        //x.push_back(i);
        //x.push_back(A[0]);
        //x.push_back(i+1);
        //x.push_back(A[1]);
        //x.push_back(i+2);
        //x.push_back(A[2]);

        int result = use_machine(x);
        if (result%2 == 0){
            A.push_back(i);
            count_A++;
        } else {
            B.push_back(i);
            count_B++;
        }

        if (result-result%2 == 0){
            A.push_back(i+1);
            A.push_back(i+2);
            count_A += 2;
            i += 3;
        } else if(result-result%2 == 4){
            B.push_back(i+1);
            B.push_back(i+2);
            count_B += 2;
            i += 3;
        } else {
            vector<int> x = { B[0], i+1, B[1], A[0], i+2, A[1], i+3, A[2], i+4 };
            //x.push_back(B[0]);
            //x.push_back(i+1);
            //x.push_back(B[1]);
            //x.push_back(A[0]);
            //x.push_back(i+2);
            //x.push_back(A[1]);
            //x.push_back(i+3);
            //x.push_back(A[2]);
            //x.push_back(i+4);

            int result = use_machine(x);
            switch(result){
                case 1:
                    B.push_back(i+1);
                    A.push_back(i+2);
                    A.push_back(i+3);
                    A.push_back(i+4);
                    count_A += 3;
                    count_B += 1;
                    break;
                case 2:
                    B.push_back(i+1);
                    A.push_back(i+2);
                    A.push_back(i+3);
                    B.push_back(i+4);
                    count_A += 2;
                    count_B += 2;
                    break;
                case 3:
                    B.push_back(i+1);
                    A.push_back(i+2);
                    B.push_back(i+3);
                    A.push_back(i+4);
                    count_A += 2;
                    count_B += 2;
                    break;
                case 4:
                    B.push_back(i+1);
                    A.push_back(i+2);
                    B.push_back(i+3);
                    B.push_back(i+4);
                    count_A += 1;
                    count_B += 3;
                    break;
                case 5:
                    A.push_back(i+1);
                    B.push_back(i+2);
                    A.push_back(i+3);
                    A.push_back(i+4);
                    count_A += 3;
                    count_B += 1;
                    break;
                case 6:
                    A.push_back(i+1);
                    B.push_back(i+2);
                    A.push_back(i+3);
                    B.push_back(i+4);
                    count_A += 2;
                    count_B += 2;
                    break;
                case 7:
                    A.push_back(i+1);
                    B.push_back(i+2);
                    B.push_back(i+3);
                    A.push_back(i+4);
                    count_A += 2;
                    count_B += 2;
                    break;
                default:
                    A.push_back(i+1);
                    B.push_back(i+2);
                    B.push_back(i+3);
                    B.push_back(i+4);
                    count_A += 1;
                    count_B += 3;
            }
            i += 5;
        }

        if (swapped) {
            swap(A, B);
            swap(count_A, count_B);
        }
    }
}


void partV4(int &i, int &n, vector<int> &A, vector<int> &B, int &count_A, int &count_B){
    while(i < n){
        bool swapped = false;
        if(A.size() < B.size()){
            swapped = true;
            swap(A, B);
            swap(count_A, count_B);
        }

        vector<int> x;
        int L = min((int)A.size(), n-i);
        for(int j=0;j<L;j++){
            x.push_back(i+j);
            x.push_back(A[j]);
        }

        int result = use_machine(x);
        if(result%2 == 0){
            A.push_back(i);
            count_A++;
        } else {
            B.push_back(i);
            count_B++;
        }
        count_B += result/2;
        count_A += (L-1) - result/2;

        if (swapped) {
            swap(A, B);
            swap(count_A, count_B);
        }
        i += L;
    }
}


int count_mushrooms(int n){
    vector<int> A = { 0 };
    vector<int> B = {};
    int count_A = 1, count_B = 0;
    int i = 1;

    if (n <= 226) {
        while(i < n){
            vector<int> x;
            x.push_back(0);
            x.push_back(i);
            int result = use_machine(x);
            if(result == 0){
                A.push_back(i);
                count_A++;
            }
            else{
                B.push_back(i);
                count_B++;
            }
            i++;
        }
        return count_A;
    }

    partV1(i, A, B, count_A, count_B);
    partV2(i, A, B, count_A, count_B);
    partV3(i, A, B, count_A, count_B);
    partV4(i, n, A, B, count_A, count_B);
    return count_A;
}

Subtask #1
100.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 0 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 7 ms 256 KB Output is correct
8 Correct 6 ms 256 KB Output is correct
9 Correct 6 ms 392 KB Output is correct
10 Correct 6 ms 256 KB Output is correct
11 Correct 7 ms 256 KB Output is correct
12 Correct 7 ms 384 KB Output is correct
13 Correct 6 ms 392 KB Output is correct
14 Correct 4 ms 256 KB Output is correct
15 Correct 7 ms 256 KB Output is correct
16 Correct 7 ms 384 KB Output is correct
17 Correct 4 ms 256 KB Output is correct
18 Correct 6 ms 256 KB Output is correct
19 Correct 7 ms 256 KB Output is correct
20 Correct 7 ms 256 KB Output is correct
21 Correct 6 ms 256 KB Output is correct
22 Correct 7 ms 256 KB Output is correct
23 Correct 6 ms 384 KB Output is correct
24 Correct 6 ms 256 KB Output is correct
25 Correct 8 ms 256 KB Output is correct
26 Correct 7 ms 256 KB Output is correct
27 Correct 7 ms 256 KB Output is correct
28 Correct 7 ms 256 KB Output is correct
29 Correct 7 ms 384 KB Output is correct
30 Correct 9 ms 256 KB Output is correct
31 Correct 9 ms 256 KB Output is correct
32 Correct 8 ms 384 KB Output is correct
33 Correct 7 ms 384 KB Output is correct
34 Correct 8 ms 256 KB Output is correct
35 Correct 9 ms 384 KB Output is correct
36 Correct 7 ms 256 KB Output is correct
37 Correct 9 ms 256 KB Output is correct
38 Correct 9 ms 256 KB Output is correct
39 Correct 7 ms 384 KB Output is correct
40 Correct 7 ms 256 KB Output is correct
41 Correct 7 ms 256 KB Output is correct
42 Correct 9 ms 256 KB Output is correct
43 Correct 7 ms 256 KB Output is correct
44 Correct 7 ms 256 KB Output is correct
45 Correct 7 ms 256 KB Output is correct
46 Correct 7 ms 384 KB Output is correct
47 Correct 7 ms 256 KB Output is correct
48 Correct 7 ms 256 KB Output is correct
49 Correct 7 ms 256 KB Output is correct
50 Correct 7 ms 256 KB Output is correct
51 Correct 7 ms 256 KB Output is correct
52 Correct 7 ms 256 KB Output is correct
53 Correct 6 ms 380 KB Output is correct
54 Correct 7 ms 256 KB Output is correct
55 Correct 6 ms 256 KB Output is correct
56 Correct 7 ms 384 KB Output is correct
57 Correct 7 ms 256 KB Output is correct
58 Correct 9 ms 256 KB Output is correct
59 Correct 7 ms 256 KB Output is correct
60 Correct 7 ms 256 KB Output is correct
61 Correct 7 ms 256 KB Output is correct
62 Correct 0 ms 256 KB Output is correct
63 Correct 1 ms 256 KB Output is correct
64 Correct 0 ms 256 KB Output is correct
65 Correct 0 ms 256 KB Output is correct
66 Correct 0 ms 256 KB Output is correct
67 Correct 1 ms 256 KB Output is correct
68 Correct 1 ms 256 KB Output is correct
69 Correct 0 ms 256 KB Output is correct
70 Correct 0 ms 256 KB Output is correct
71 Correct 1 ms 256 KB Output is correct
72 Correct 0 ms 256 KB Output is correct
73 Correct 1 ms 256 KB Output is correct
74 Correct 0 ms 256 KB Output is correct
75 Correct 0 ms 256 KB Output is correct
76 Correct 0 ms 256 KB Output is correct
77 Correct 0 ms 256 KB Output is correct
78 Correct 1 ms 256 KB Output is correct
79 Correct 1 ms 256 KB Output is correct
80 Correct 0 ms 256 KB Output is correct
81 Correct 1 ms 256 KB Output is correct
82 Correct 1 ms 256 KB Output is correct
83 Correct 0 ms 256 KB Output is correct
84 Correct 0 ms 256 KB Output is correct
85 Correct 1 ms 256 KB Output is correct
86 Correct 1 ms 256 KB Output is correct
87 Correct 1 ms 256 KB Output is correct
88 Correct 1 ms 256 KB Output is correct
89 Correct 1 ms 256 KB Output is correct
90 Correct 1 ms 256 KB Output is correct
91 Correct 1 ms 256 KB Output is correct