Submission #553039

#	Time	Username	Problem	Language	Result	Execution time	Memory
553039		fcmalkcin	Cave (IOI13_cave)	C++17	100 / 100	1718 ms	648 KiB

cave

#include "cave.h"

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

#define ll int
#define pll pair<ll,ll>
#define ff first
#define ss second
//#define endl "\n"
#define pb push_back
#define F(i,a,b) for(ll i=a;i<=b;i++)

const ll maxn=5e3+100;
const ll base=2e9;
const ll mod= 1e9+7 ;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

ll a[maxn];
ll b[maxn];
ll c[maxn];
ll msk[maxn];
ll col[maxn];
ll res[maxn];

ll tryCombination1(vector<ll> vt)
{
    for (int i=0;i<vt.size();i++) a[i]=vt[i];
    return tryCombination(a);
}
void answer1(vector<ll> vt,vector<ll> vt1)
{
    for (int i=0;i<vt.size();i++) a[i]=vt[i],b[i]=vt1[i];
    answer(a,b);
}
void exploreCave(ll n)
{
    memset(col,0,sizeof(col));
    ll p=-1;
    for (int t=0; t<14; t++)
    {
        if ((1ll<<t)<n)
        {
            p=t;
        }
    }
    p++;
    for (int i=0; i<n; i++)
    {
        ll msknxt=0;
        vector<ll> vt;
        for (int i=0; i<n; i++)
        {
            if (col[i])
            {
                vt.pb(col[i]-1);
            }
            else
            {
                vt.pb(0);
            }
        }
        ll h=tryCombination1(vt);
        if (h==-1)
            h=n;
        ll t=1;
        assert(h>=i);
        if (h==i)
            t=0;
   //     cout <<t<<" "<<i<<" "<<h<<" chk2"<<endl;
        for (int j=0; j<p; j++)
        {
            vector<ll> vt;
            for (int i=0; i<n; i++)
            {
                if (col[i])
                {
                    vt.pb(col[i]-1);
                }
                else
                {
                    if (i&(1ll<<j))
                    {
                        vt.pb(1^t);
                    }
                    else
                    {
                        vt.pb(0^t);
                    }
                }
            }
            ll h=tryCombination1(vt);
            /*if (i==0)
            {
                cout <<h<<" "<<j<<" wtf"<<endl;
                for (auto p:vt) cout <<p<<" ";
                cout <<endl;
            }*/
            if (h==-1)
                h=n;
            if (h>i)
            {
                msknxt+=(1ll<<j);
            }
        }
      //  cout <<msknxt<<" chk3"<<endl;
        col[msknxt]=(1-t)+1;
        res[msknxt]=i;
    }
    vector<ll> vt;
    vector<ll> vt1;
    for (int i=0; i<n; i++)
        vt.pb(col[i]-1),vt1.pb(res[i]);
    answer1(vt,vt1);
}

Compilation message (stderr)

cave.cpp: In function 'int tryCombination1(std::vector<int>)':
cave.cpp:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i=0;i<vt.size();i++) a[i]=vt[i];
      |                  ~^~~~~~~~~~
cave.cpp: In function 'void answer1(std::vector<int>, std::vector<int>)':
cave.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i=0;i<vt.size();i++) a[i]=vt[i],b[i]=vt1[i];
      |                  ~^~~~~~~~~~

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