Submission #212151

#	Time	Username	Problem	Language	Result	Execution time	Memory
212151		Nucleist	Chameleon's Love (JOI20_chameleon)	C++14	40 / 100	105 ms	816 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h> 
using namespace std; 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define INF 1000000000
#define MOD 1000000007
#define pb push_back
#define ve vector<int>
#define dos pair<ll,ll>
#define vedos vector<dos>
#define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
struct greateri
{
    template<class T>
    bool operator()(T const &a, T const &b) const { return a > b; }
};
int sex[5001];
map<int,int>gg;
int posi[5001][3];
ve posia[5001];
int vis[2001];
int yhebha[3001];
bool nal[2001];
bool ka1[5001];
int cores[5001];
int addi(int x,int l,int r,int cur)
{
    if(posi[cur][0]>=l && posi[cur][0]<=r)x++;
    if(posi[cur][1]>=l && posi[cur][1]<=r)x++;
    return x;
}
void Solve(int N)
{
    memset(posi,-1,sizeof posi);
    memset(cores,-1,sizeof cores);
    set<int>unknown;
    N*=2;
    for (int i = 1; i<N; ++i)
    {
       unknown.insert(i);
    }
    sex[0]=0;
    queue<int>yo;
    yo.push(0);
    while(!yo.empty())
    {
        auto u=yo.front();
        yo.pop();
        set<int>ko=unknown;
        for(auto it:ko)
        {
        	ve hi;
        	hi.pb(u+1);hi.pb(it+1);
            if(Query(hi)==1)
            {
                sex[it]=1-sex[u];
                yo.push(it);
                unknown.erase(it);
            }
        }
        if(yo.size()==0 && unknown.size()!=0){yo.push(*(unknown.begin()));unknown.erase(*(unknown.begin()));}
    }
    ve male,female;
    for (int i = 0; i < N; ++i)
    {
        if(!sex[i])
        {
            male.pb(i);
        }
        else
        {
            female.pb(i);
        }
    }
    memset(yhebha,-1,sizeof yhebha);
    for (int i = 0; i < male.size(); ++i)
    {
    	memset(nal,0,sizeof nal);
        int low=0,high=female.size()-1;
        int cur=male[i];
        debug(cur);
        int posi1=-1,posi2=-1,posi3=-1;
        while(low<=high)
        {
            int med=(low+high)/2;
            ve yo;
            yo.pb(cur+1);
            for (int i=low; i <= med; ++i)
            {
            	if(!nal[i])
                yo.pb(female[i]+1);
            }
            for(auto it:yo)debug(it);
            int kol=Query(yo);
            debug(kol);
            debugs(med,low);
            //kol=addi(kol,low,med,cur); 
            if(low==high)
            {
                if(kol==yo.size())
                {
                    posi1=-1;
                }
                else
                {
                    posi1=low;
                }
                break;
            }
            if(kol==yo.size())
            {
                low=med+1;
            }
            else
            {
                high=med;
            }
        }
        low=0,high=female.size()-1;
        debugs(female[posi1],cur);
        nal[posi1]=1;
        posi[cur][0]=female[posi1];
        posia[female[posi1]].pb(cur);
        while(low<=high)
        {
            int med=(low+high)/2;
            ve yo;
            yo.pb(cur+1);
            for (int i = low; i <= med; ++i)
            {
            	if(!nal[i])
                {yo.pb(female[i]+1);debug(female[i]+1);}
            }
            int kol=Query(yo);
            //kol=addi(kol,low,med,cur);

            if(low==high)
            {
                if(kol==yo.size())
                {
                    posi2=-1;
                }
                else
                {
                    posi2=low;
                }
                break;
            }
            if(kol==yo.size())
            {
                low=med+1;
            }
            else
            {
                high=med;
            }
        }
        low=0,high=female.size()-1;
        if(posi2!=-1)posi[cur][1]=female[posi2];
        else posi[cur][1]=-1;
        //debugs(female[posi2],cur);
        nal[posi2]=1;
        posia[female[posi1]].pb(cur);
        while(low<=high)
        {
            int med=(low+high)/2;
            ve yo;
            yo.pb(cur+1);
            for (int i = low; i <= med; ++i)
            {
            	if(!nal[i])
                {yo.pb(female[i]+1);debug(female[i]+1);}
            }
            int kol=Query(yo);

            //kol=addi(kol,low,med,cur);
            if(low==high)
            {
                if(kol==yo.size())
                {
                    posi3=-1;
                }
                else
                {
                    posi3=low;
                }    
                break;
            }
            if(kol==yo.size())
            {
                low=med+1;
            }
            else
            {
                high=med;
            }
        }
        if(posi3!=-1)posi[cur][2]=female[posi3];
        else posi[cur][2]=-1;
        if(posi2==-1 && posi3==-1)
        {
            ka1[cur]=1;
            debugs(posi1,female[posi1]);
            debugs(cur,female[posi1]);
            Answer(cur+1,female[posi1]+1);
            cores[female[posi1]]=cur;
        }
        posia[female[posi1]].pb(cur);
    }
    //debug(0);
    bool ka=false;
    for (int i = 0; i < male.size(); ++i)
    {
        int cur=male[i];
        
        if(posi[cur][1]!=-1)
        {
            ve di;
            di.pb(cur+1);
            di.pb(posi[cur][0]+1);
            di.pb(posi[cur][1]+1);
            int yo = Query(di);
        	ve ka,fa;
        	ka.pb(cur+1);ka.pb(posi[cur][0]+1);ka.pb(posi[cur][2]+1);
        	fa.pb(cur+1);fa.pb(posi[cur][2]+1);fa.pb(posi[cur][1]+1);
            int so = Query(ka);
            int ko = Query(fa);
            if(yo==1)
            {
               yhebha[posi[cur][2]]=cur;
               debugs(posi[cur][2],cur);
               vis[cur]=1;
            }
            else if(so==1)
            {
                yhebha[posi[cur][1]]=cur;
                debugs(posi[cur][1],cur);
                vis[cur]=2;
            }
            else
            {
                yhebha[posi[cur][0]]=cur;
                vis[cur]=3;
                debugs(posi[cur][0],cur);
                debugs(cur,vis[cur]);
            }
        }
    }
    //vis[6]=3;
    for (int i = 0; i < male.size(); ++i)
    {
        int cur=male[i];
        int fem1=0,fem2=0;
        if(!ka1[cur])
        {
            debugs(cur,vis[cur]);
        //int yo = Query([cur,posi[cur][0],posi[cur][1]]);
        if(vis[cur]<=1)
        {
            fem1=posi[cur][0];
            fem2=posi[cur][1];
        }
        else if(vis[cur]==2)
        {
            fem1=posi[cur][0];
            fem2=posi[cur][2];
        }
        else
        {
            fem1=posi[cur][1];
            fem2=posi[cur][2];
            debugs(posi[cur][1],posi[cur][2]);
        }
        {
            if(yhebha[fem1]==-1 || yhebha[fem1]==cur)swap(fem1,fem2);
            ve lom;
            debug(yhebha[fem1])
            lom.pb(cur+1);
            lom.pb(fem1+1);
            lom.pb(yhebha[fem1]+1);
            int sol=Query(lom);
            debugs(cores[fem1],cores[fem2]);
            if(sol==1 || cores[fem2]!=-1)
            {
                debugs(cur,fem1);
                Answer(cur+1,fem1+1);
            }
            else
            {
                debugs(cur,fem2);
                Answer(cur+1,fem2+1);
            }
        }}
    }
}
//code the AC sol !
// BS/queue/map
/*
4
1 0 1 0 0 1 1 0
4 4 1 2 1 2 3 3
4 3 8 7 6 5 2 1
*/

Compilation message (stderr)

chameleon.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
chameleon.cpp:6:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:84:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < male.size(); ++i)
                     ~~^~~~~~~~~~~~~
chameleon.cpp:108:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(kol==yo.size())
                    ~~~^~~~~~~~~~~
chameleon.cpp:118:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(kol==yo.size())
                ~~~^~~~~~~~~~~
chameleon.cpp:147:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(kol==yo.size())
                    ~~~^~~~~~~~~~~
chameleon.cpp:157:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(kol==yo.size())
                ~~~^~~~~~~~~~~
chameleon.cpp:187:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(kol==yo.size())
                    ~~~^~~~~~~~~~~
chameleon.cpp:197:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(kol==yo.size())
                ~~~^~~~~~~~~~~
chameleon.cpp:220:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < male.size(); ++i)
                     ~~^~~~~~~~~~~~~
chameleon.cpp:235:17: warning: unused variable 'ko' [-Wunused-variable]
             int ko = Query(fa);
                 ^~
chameleon.cpp:258:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < male.size(); ++i)
                     ~~^~~~~~~~~~~~~
chameleon.cpp:219:10: warning: unused variable 'ka' [-Wunused-variable]
     bool ka=false;
          ^~

• Subtask 1: 0 / 4
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36