oj.uz

Submission #954385

# Submission time Handle Problem Language Result Execution time Memory
954385 2024-03-27T18:19:32 Z andrei_boaca Chameleon's Love (JOI20_chameleon) C++17
44 / 100
 46 ms 1028 KB 
#include "chameleon.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
namespace
{
    vector<int> muchii[1005];
    int n;
    int cul[1005];
    int p[1005],par[1005];
    bool use[1005];
    int nr[1005];
    void dfs(int nod)
    {
        for(int i:muchii[nod])
            if(cul[i]==-1)
            {
                cul[i]=1-cul[nod];
                dfs(i);
            }
    }
    void plsfind(vector<int> v,int me)
    {
        bool ok=0;
        if(me==4)
            ok=1;
        if(v.empty())
            return;
        int st=0;
        int dr=v.size();
        dr--;
        int poz=1e9;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            vector<int> nodes;
            nodes.push_back(me);
            for(int i=0;i<=mij;i++)
                nodes.push_back(v[i]);
            int val=Query(nodes);
            if(val<nodes.size())
            {
                poz=mij;
                dr=mij-1;
            }
            else
                st=mij+1;
        }
        if(poz>=v.size())
            return;
        muchii[me].push_back(v[poz]);
        muchii[v[poz]].push_back(me);
        vector<int> aux;
        for(int i=poz+1;i<v.size();i++)
            aux.push_back(v[i]);
        plsfind(aux,me);
    }
}
void Solve(int N)
{
    n=N;
    for(int i=2;i<=2*n;i++)
    {
        for(int j=1;j<=2*n;j++)
            cul[j]=-1;
        for(int j=1;j<i;j++)
            if(cul[j]==-1)
            {
                cul[j]=0;
                dfs(j);
            }
        vector<int> a,b;
        for(int j=1;j<i;j++)
        {
            if(cul[j]==0)
                a.push_back(j);
            else
                b.push_back(j);
        }
        plsfind(a,i);
        plsfind(b,i);
    }
    for(int i=1;i<=2*n;i++)
    {
        int lg=muchii[i].size();
        if(muchii[i].size()==3)
        {
            for(int j=0;j<muchii[i].size();j++)
                nr[j]=0;
            for(int j=0;j<muchii[i].size();j++)
                for(int k=j+1;k<muchii[i].size();k++)
                {
                    int val=Query({i,muchii[i][j],muchii[i][k]});
                    if(val==2)
                    {
                        nr[j]++;
                        nr[k]++;
                    }
                }
            for(int j=0;j<muchii[i].size();j++)
                if(nr[j]==2)
                    p[i]=muchii[i][j];
        }
    }
    for(int i=1;i<=2*n;i++)
    {
        if(p[i]==0)
        {
            if(use[i])
                continue;
            Answer(i,muchii[i][0]);
            use[i]=1;
            use[muchii[i][0]]=1;
            continue;
        }
        vector<int> nodes;
        int nod=i;
        while(true)
        {
            if(nod==i&&nodes.size()>0)
                break;
            nodes.push_back(nod);
            int fiu=p[nod];
            par[fiu]=nod;
            nod=fiu;
        }
        for(int j:nodes)
            if(!use[j])
            {
                int a=muchii[j][0]^muchii[j][1]^muchii[j][2]^par[j]^p[j];
                use[a]=1;
                use[j]=1;
                Answer(a,j);
            }
    }
}

Compilation message

chameleon.cpp: In function 'void {anonymous}::plsfind(std::vector<int>, int)':
chameleon.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             if(val<nodes.size())
      |                ~~~^~~~~~~~~~~~~
chameleon.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         if(poz>=v.size())
      |            ~~~^~~~~~~~~~
chameleon.cpp:54:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int i=poz+1;i<v.size();i++)
      |                         ~^~~~~~~~~
chameleon.cpp:24:14: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   24 |         bool ok=0;
      |              ^~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:88:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |             for(int j=0;j<muchii[i].size();j++)
      |                         ~^~~~~~~~~~~~~~~~~
chameleon.cpp:90:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |             for(int j=0;j<muchii[i].size();j++)
      |                         ~^~~~~~~~~~~~~~~~~
chameleon.cpp:91:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |                 for(int k=j+1;k<muchii[i].size();k++)
      |                               ~^~~~~~~~~~~~~~~~~
chameleon.cpp:100:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             for(int j=0;j<muchii[i].size();j++)
      |                         ~^~~~~~~~~~~~~~~~~
chameleon.cpp:85:13: warning: unused variable 'lg' [-Wunused-variable]
   85 |         int lg=muchii[i].size();
      |             ^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 46 ms 1028 KB Output is correct
4 Correct 40 ms 344 KB Output is correct
5 Correct 40 ms 344 KB Output is correct
6 Correct 41 ms 536 KB Output is correct
7 Correct 40 ms 344 KB Output is correct
8 Correct 40 ms 540 KB Output is correct
9 Correct 41 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 2 ms 540 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 2 ms 344 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 46 ms 1028 KB Output is correct
4 Correct 40 ms 344 KB Output is correct
5 Correct 40 ms 344 KB Output is correct
6 Correct 41 ms 536 KB Output is correct
7 Correct 40 ms 344 KB Output is correct
8 Correct 40 ms 540 KB Output is correct
9 Correct 41 ms 340 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 2 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 2 ms 540 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 2 ms 344 KB Output is correct
28 Correct 0 ms 344 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Incorrect 37 ms 568 KB Wrong Answer [3]
31 Halted 0 ms 0 KB -