oj.uz

답안 #212169

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
212169 2020-03-22T12:03:36 Z Nucleist 카멜레온의 사랑 (JOI20_chameleon) C++14
40 / 100
 3000 ms 6520 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);
    }
    if(N/2<=50)
    {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()));}
    }}
    else
    {for (int i = N/2; i < N; ++i)
    {
        sex[i]=1;
    }}
    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:101:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < male.size(); ++i)
                     ~~^~~~~~~~~~~~~
chameleon.cpp:125:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(kol==yo.size())
                    ~~~^~~~~~~~~~~
chameleon.cpp:135:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(kol==yo.size())
                ~~~^~~~~~~~~~~
chameleon.cpp:164:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(kol==yo.size())
                    ~~~^~~~~~~~~~~
chameleon.cpp:174:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(kol==yo.size())
                ~~~^~~~~~~~~~~
chameleon.cpp:204:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(kol==yo.size())
                    ~~~^~~~~~~~~~~
chameleon.cpp:214:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(kol==yo.size())
                ~~~^~~~~~~~~~~
chameleon.cpp:237:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < male.size(); ++i)
                     ~~^~~~~~~~~~~~~
chameleon.cpp:252:17: warning: unused variable 'ko' [-Wunused-variable]
             int ko = Query(fa);
                 ^~
chameleon.cpp:275:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < male.size(); ++i)
                     ~~^~~~~~~~~~~~~
chameleon.cpp:236:10: warning: unused variable 'ka' [-Wunused-variable]
     bool ka=false;
          ^~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Incorrect 20 ms 640 KB Wrong Answer [5]
4 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 6 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 9 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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 6 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 9 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 100 ms 760 KB Output is correct
11 Correct 88 ms 640 KB Output is correct
12 Correct 92 ms 760 KB Output is correct
13 Correct 102 ms 760 KB Output is correct
14 Correct 102 ms 764 KB Output is correct
15 Correct 101 ms 764 KB Output is correct
16 Correct 97 ms 760 KB Output is correct
17 Correct 96 ms 760 KB Output is correct
18 Correct 113 ms 760 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Execution timed out 3078 ms 6520 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Incorrect 20 ms 640 KB Wrong Answer [5]
4 Halted 0 ms 0 KB -