Submission #919455

#	Time	Username	Problem	Language	Result	Execution time	Memory
919455		Gwynbleidd_	동굴 (IOI13_cave)	C++17	0 / 100	283 ms	628 KiB

cave

#include "cave.h"

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> flip, pos;

int comb(vector<int>& a){
    int q[n];
    for(int i=0;i<n;i++) q[i]=a[i];
    return tryCombination(q);
}

void answer(){
    int f[n], p[n];
    for(int i=0;i<n;i++) f[i]=flip[i], p[i]=pos[i];
    answer(f,p);
}

void dac(vector<int>& a, vector<int>& ind, int last){
    if(ind.size()==1){
        if(last==-1){
            flip[ind[0]]=a[ind[0]];
            a[ind[0]]=1-a[ind[0]];
            pos[ind[0]]=comb(a);
        }
        else{
            flip[ind[0]]=1-a[ind[0]];
            pos[ind[0]]=last;
        }
    }
    else {
        vector<int> l,r;
        for(int i=0;i<ind.size();i++){
            if(i<ind.size()/2){
                a[ind[i]]=1-a[ind[i]];
                l.push_back(ind[i]);
            }
            else{
                r.push_back(ind[i]);
            }
        }
        int x=comb(a);
        if(last==-1){
            dac(a,l,x);
        }
        else if(x==last){
            for(int i=0;i<l.size();i++){
                a[l[i]]=1-a[l[i]];
            }
            dac(a,r,last);
        }
        else{
            dac(a,l,last);
        }
    }
}

void exploreCave(int N) {
    n=N;
    flip.assign(n,-1);
    pos.assign(n,-1);
    for(int t=0;t<n;t++){
        vector<int> a(n),ind;
        for(int i=0;i<n;i++){
            if(flip[i]!=-1){
                a[i]=flip[i];
            }
            else{
                ind.push_back(i);
                a[i]=0;
            }
        }
        if(!ind.size()){
            break;
        }
        dac(a,ind,comb(a));
    }
    answer();
}

Compilation message (stderr)

cave.cpp: In function 'void dac(std::vector<int>&, std::vector<int>&, int)':
cave.cpp:36:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int i=0;i<ind.size();i++){
      |                     ~^~~~~~~~~~~
cave.cpp:37:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             if(i<ind.size()/2){
      |                ~^~~~~~~~~~~~~
cave.cpp:50:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             for(int i=0;i<l.size();i++){
      |                         ~^~~~~~~~~

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