Submission #962721

#	Time	Username	Problem	Language	Result	Execution time	Memory
962721		simona1230	Cave (IOI13_cave)	C++17	100 / 100	659 ms	1040 KiB

cave

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

int n;
int c[5000],d[5000];
int p[5000],l[5000];
int used[5000];
void exploreCave(int N)
{
    n=N;
    int x=tryCombination(l);
    if(x==-1)
    {
        x=0;
        for(int i=0; i<n; i++)
            c[i]=1;
    }

    for(int i=0; i<n-1; i++)
    {
        /*cout<<endl;
        for(int j=0; j<n; j++)
            cout<<c[j]<<" ";
        cout<<endl;

        for(int j=0; j<n; j++)
            cout<<used[j]<<" ";
        cout<<endl;
        cout<<i<<" / "<<x<<endl;*/

        int l=1,r=n-i;
        while(l!=r)
        {
            int m=(l+r)/2;
            int cnt=0;
            for(int j=0; j<n; j++)
            {
                if(!used[j])
                {
                    //cout<<"=-=- "<<j<<endl;
                    cnt++;
                    if(cnt>=l&&cnt<=m)p[j]=c[j]^1;
                    else p[j]=c[j];
                }
                else p[j]=c[j];

            }
            int y=tryCombination(p);

            /*cout<<l<<" "<<m<<" "<<r<<endl;
            for(int j=0; j<n; j++)
                cout<<p[j]<<" ";
            cout<<endl;
            cout<<"* "<<y<<endl;*/
            if(y==-1&&x==i||x==i&&x!=y||x!=i&&i==y)
            {
                //cout<<"f"<<endl;
                r=m;
            }
            else
            {
                l=m+1;
            }
        }

        int cnt=0;
        for(int j=0; j<n; j++)
        {
            if(!used[j])
            {
                cnt++;
                if(cnt==l)
                {
                    used[j]=1;
                    if(x==i)c[j]=1^c[j];
                    d[j]=i;
                    //cout<<"- "<<j<<endl;
                }
            }
        }

        x=tryCombination(c);
    }
    int lf=0;
    for(int j=0;j<n;j++)
    {
        if(!used[j])
        {
            d[j]=n-1;
            if(x!=-1)c[j]=c[j]^1;
            lf=j;
        }
    }
    answer(c,d);
}

/*
10
1 0 0 1 1 1 0 1 1 0
6 5 9 0 1 7 4 2 3 8
*/

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:56:21: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   56 |             if(y==-1&&x==i||x==i&&x!=y||x!=i&&i==y)
      |                ~~~~~^~~~~~
cave.cpp:56:45: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   56 |             if(y==-1&&x==i||x==i&&x!=y||x!=i&&i==y)
      |                                         ~~~~^~~~~~
cave.cpp:85:9: warning: variable 'lf' set but not used [-Wunused-but-set-variable]
   85 |     int lf=0;
      |         ^~

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