oj.uz

Submission #212151

# Submission time Handle Problem Language Result Execution time Memory
212151 2020-03-22T11:22:02 Z Nucleist Chameleon's Love (JOI20_chameleon) C++14
40 / 100
 105 ms 816 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;
}
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

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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Incorrect 23 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 512 KB Output is correct
2 Correct 5 ms 536 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 7 ms 512 KB Output is correct
5 Correct 7 ms 512 KB Output is correct
6 Correct 8 ms 512 KB Output is correct
7 Correct 7 ms 512 KB Output is correct
8 Correct 8 ms 512 KB Output is correct
9 Correct 7 ms 640 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 536 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 7 ms 512 KB Output is correct
5 Correct 7 ms 512 KB Output is correct
6 Correct 8 ms 512 KB Output is correct
7 Correct 7 ms 512 KB Output is correct
8 Correct 8 ms 512 KB Output is correct
9 Correct 7 ms 640 KB Output is correct
10 Correct 88 ms 640 KB Output is correct
11 Correct 88 ms 716 KB Output is correct
12 Correct 93 ms 640 KB Output is correct
13 Correct 94 ms 760 KB Output is correct
14 Correct 100 ms 816 KB Output is correct
15 Correct 92 ms 760 KB Output is correct
16 Correct 94 ms 760 KB Output is correct
17 Correct 105 ms 732 KB Output is correct
18 Correct 100 ms 640 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 616 KB Output is correct
2 Correct 7 ms 640 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 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Incorrect 23 ms 640 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -