Submission #993494

#	Time	Username	Problem	Language	Result	Execution time	Memory
993494		Rifal	Cave (IOI13_cave)	C++14	100 / 100	970 ms	848 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
    int now[N] = {}, D[N] = {};
    int x = tryCombination(now);
    for(int i = 0; i < N; i++) now[i] = -1;
    int cur = 0;
    for(int i = 0; i < N; i++) {
        int num1, num2;
        //cout << x << ' ' << i << 'w' << endl;
        if(x != i) {
            num1 = abs(1 - cur);
            num2 = cur;
        }
        else {
            num1 = cur;
            num2 = abs(1 - cur);
        }
        int l = 0, r = N-1;
        vector<int> pos;
        while(l < r) {
            int mid = (l+r-1)/2;
            pos.clear();
            for(int j = 0; j < N; j++) {
                if(now[j] == -1) {
                    if(j >= l && j <= mid) now[j] = num1;
                    else now[j] = num2;
                    pos.push_back(j);
                }
            }
            x = tryCombination(now);
         //   for(int j = 0; j < N; j++) cout << now[j] << ' ';
         //   cout << endl;
         //   cout << num1 << ' ' << num2 << 'u' << endl;
          //  cout << i << ' ' << x << ' ' <<  l << ' ' << mid << ' ' << r << 'p' << endl;
            if(x == i) r = mid;
            else l = mid+1;
            for(int j = 0; j < pos.size(); j++) now[pos[j]] = -1;
        }
        pos.clear();
      //  cout << l << 'z' << endl;
        D[l] = i;
        now[l] = abs(1 - num1);
        for(int j = 0; j < N; j++) {
            if(now[j] == -1) {
                now[j] = 0;
                pos.push_back(j);
             }
        }
        cur = 0;
         x = tryCombination(now);
        //for(int j = 0; j < N; j++) cout << now[j] << ' ';
      //  cout << endl;
      //  cout << x << ' ' << i+1 << 'q' << endl;
        for(int j = 0; j < pos.size(); j++) now[pos[j]] = -1;
    }
    answer(now,D);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:39:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             for(int j = 0; j < pos.size(); j++) now[pos[j]] = -1;
      |                            ~~^~~~~~~~~~~~
cave.cpp:56:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(int j = 0; j < pos.size(); j++) now[pos[j]] = -1;
      |                        ~~^~~~~~~~~~~~

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