oj.uz

Submission #212161

# Submission time Handle Problem Language Result Execution time Memory
212161 2020-03-22T11:33:43 Z Nucleist Chameleon's Love (JOI20_chameleon) C++14
40 / 100
 111 ms 1020 KB 
#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;
}
int bestiole[5001];
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;
        set<int>nexti;
        for(auto it:ko)
        {
        	ve hi;
        	hi.pb(u+1);hi.pb(it+1);
            if(Query(hi)==1)
            {
                sex[it]=1-sex[u];
                nexti.insert(it);
                bestiole[u]++;
                bestiole[it]++;
                unknown.erase(it);
            }
        }
        if(bestiole[u]!=1)
        {
            for(auto it:nexti)
            {   
                yo.push(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

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:95:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < male.size(); ++i)
                     ~~^~~~~~~~~~~~~
chameleon.cpp:119:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(kol==yo.size())
                    ~~~^~~~~~~~~~~
chameleon.cpp:129:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(kol==yo.size())
                ~~~^~~~~~~~~~~
chameleon.cpp:158:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(kol==yo.size())
                    ~~~^~~~~~~~~~~
chameleon.cpp:168:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(kol==yo.size())
                ~~~^~~~~~~~~~~
chameleon.cpp:198:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(kol==yo.size())
                    ~~~^~~~~~~~~~~
chameleon.cpp:208:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(kol==yo.size())
                ~~~^~~~~~~~~~~
chameleon.cpp:231:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < male.size(); ++i)
                     ~~^~~~~~~~~~~~~
chameleon.cpp:246:17: warning: unused variable 'ko' [-Wunused-variable]
             int ko = Query(fa);
                 ^~
chameleon.cpp:269:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < male.size(); ++i)
                     ~~^~~~~~~~~~~~~
chameleon.cpp:230:10: warning: unused variable 'ka' [-Wunused-variable]
     bool ka=false;
          ^~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Incorrect 24 ms 640 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 9 ms 512 KB Output is correct
5 Correct 7 ms 688 KB Output is correct
6 Correct 7 ms 640 KB Output is correct
7 Correct 7 ms 512 KB Output is correct
8 Correct 8 ms 512 KB Output is correct
9 Correct 8 ms 640 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 9 ms 512 KB Output is correct
5 Correct 7 ms 688 KB Output is correct
6 Correct 7 ms 640 KB Output is correct
7 Correct 7 ms 512 KB Output is correct
8 Correct 8 ms 512 KB Output is correct
9 Correct 8 ms 640 KB Output is correct
10 Correct 87 ms 712 KB Output is correct
11 Correct 87 ms 760 KB Output is correct
12 Correct 111 ms 1020 KB Output is correct
13 Correct 97 ms 760 KB Output is correct
14 Correct 97 ms 764 KB Output is correct
15 Correct 93 ms 756 KB Output is correct
16 Correct 95 ms 760 KB Output is correct
17 Correct 101 ms 760 KB Output is correct
18 Correct 94 ms 708 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Incorrect 24 ms 640 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Incorrect 24 ms 640 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -