oj.uz

Submission #1079819

# Submission time Handle Problem Language Result Execution time Memory
1079819 2024-08-29T02:06:06 Z HD1 Counting Mushrooms (IOI20_mushrooms) C++14
0 / 100
 0 ms 344 KB 
#include "mushrooms.h"
#include <vector>
#include <iostream>
using namespace std;

int count_mushrooms(int n) {
    if(n < 100){
        int res = 1;
        for(int i = 2; i <= n;i++){
            int ans = use_machine({0,i-1});
            res += 1 - ans;
        }
        return res;
    }
    int k = -1,mini = 1e9;
    for(int i = 1; i < n; i++){
        int v = 2*i + ( n - (2*i + 1 ) +i)/(i+1);
        if(mini > v) mini = v, k = i;
    }
    bool isA = true;
    vector<int> A,B;
    A.push_back(1);
    for(int i = 2; i <= 3;i++){
        int ans = use_machine({0,i-1});
        if(ans == 0) A.push_back(i);
        else B.push_back(i); 
    } 
    int x,y, go = true;
    if(B.size() > A.size()) x = B[0], y = B[1], go = false;
    else x = A[0], y = A[1];

    for(int i = 4; i <= 2*k+2;i+=2){
        int ans = use_machine({i-1,y,i,x});
    
        if(!go){
            if( ans == 0) B.push_back(i), B.push_back(i+1);
            else if( ans == 1)  A.push_back(i), B.push_back(i+1);
            else if( ans == 2)  B.push_back(i), A.push_back(i+1);
            else A.push_back(i), A.push_back(i+1);
        }
        else{
            if( ans == 3) B.push_back(i), B.push_back(i+1);
            else if( ans == 2)  A.push_back(i), B.push_back(i+1);
            else if( ans == 1)  B.push_back(i), A.push_back(i+1);
            else A.push_back(i), A.push_back(i+1);
        }
    } 
    int res = A.size();
    if(B.size() > A.size()) swap(A,B), isA = false;
    

    for(int i = 1; i <= ( n - (2*k + 1 ) +k)/(k+1); i++){
        int ini = 2*k+2 + (i-1)*(k+1) ;
        int fin = min(n+1, 2*k+2 + (i)*(k+1));
        vector<int> q;

        for(int j = ini; j < fin; j++){
            q.push_back(j-1);
            q.push_back(A[j-ini]-1);
        }
        
        int ans = use_machine(q);
        if(ans&1) ans = 1 + ans/2;
        else ans = ans/2;
        res += ( isA ? fin-ini-ans : ans);
    
    }

    return res;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 0 ms 344 KB Duplicate value 3 in the query array.
6 Halted 0 ms 0 KB -