Submission #846827

#	Time	Username	Problem	Language	Result	Execution time	Memory
846827		Elvin_Fritl	Cave (IOI13_cave)	C++17	100 / 100	172 ms	848 KiB

cave

#include "cave.h"

#include <bits/stdc++.h>
using namespace std;

void exploreCave(int n)
{
    int v[n],res[n];
    vector<int>ind;
    for(int i=0;i<n;i++){
        ind.push_back(i);
    }
    for(int i=0;i<n;i++){
        for(auto &j:ind){
            v[j] = 0;
        }
        int k = tryCombination(v);
        ///cerr << k << endl;
        if(k == -1 || k > i){
            for(auto &j:ind){
                v[j] = 1;
            }
            int l = 1 , r = ind.size();
            auto chek = [&](int ml,int mr) -> bool {
                for(int j=ml;j<=mr;j++){
                    v[ind[j]]++;
                    v[ind[j]]%=2;
                    ///cerr << v[ind[j]] << "    ";
                }
                ///cerr << endl;
                int tmp = tryCombination(v);
                for(int j=ml;j<=mr;j++){
                    v[ind[j]]++;
                    v[ind[j]]%=2;
                    ///cerr << v[ind[j]] << "   ";
                }
                ///cerr << endl;
                return ((tmp > i) || (tmp == -1));
            };
            int ans = -1;
            while(l < r){
                int mid=(l+r)>>1;
                ///cerr<<"typ 0 :: \n";
                if(chek(l-1,mid-1)){
                    r = mid;
                }
                else{
                    l = mid + 1;
                }
            }
            ans = r;
            ///cout<<ind[ans - 1]<<"   "<<ind.size()<<endl;
            assert(ans - 1 < ind.size());
            v[ind[ans - 1]] = 0;
            res[ind[ans - 1]] = i;
            if(find(ind.begin(),ind.end(),ind[ans - 1]) != ind.end())
                ind.erase(find(ind.begin(),ind.end(),ind[ans - 1]));
        }
        else{
            int l = 1 , r = ind.size();
            auto chek = [&](int ml,int mr) -> bool {
                for(int j=ml;j<=mr;j++){
                    v[ind[j]]++;
                    v[ind[j]]%=2;
                    ///cerr << v[ind[j]] << "    ";
                }
                ///cerr << endl;
                int tmp = tryCombination(v);
                ///cerr << tmp << endl;
                for(int j=ml;j<=mr;j++){
                    v[ind[j]]++;
                    v[ind[j]]%=2;
                    ///cerr << v[ind[j]] << "   ";
                }
                ///cerr << endl;
                return ((tmp > i) || (tmp == -1));
            };
            while(l < r){
                int mid=(l+r)>>1;
                ///cerr<<"typ 1 :: \n";
                if(chek(l-1,mid-1)){
                    r = mid;
                }
                else{
                    l = mid + 1;
                }
            }
            int ans = r;
            ///cout<<ind[ans - 1]<<"   "<<ind.size()<<endl;
            res[ind[ans - 1]] = i;
            v[ind[ans - 1]] = 1;
            if(find(ind.begin(),ind.end(),ind[ans - 1]) != ind.end()){
                ind.erase(find(ind.begin(),ind.end(),ind[ans - 1]));
            }
        }
    }

    answer(v,res);
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from cave.cpp:3:
cave.cpp: In function 'void exploreCave(int)':
cave.cpp:53:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             assert(ans - 1 < ind.size());
      |                    ~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24