oj.uz

Submission #212411

# Submission time Handle Problem Language Result Execution time Memory
212411 2020-03-22T21:57:54 Z Rayaabualjamal Chameleon's Love (JOI20_chameleon) C++14
44 / 100
 62 ms 512 KB 
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iomanip> 
#define rep(i, a, b) for (int i = a; i < b; i++)
#define per(j, a, b) for (int j = a; j >= b; j--)
#include "chameleon.h"
#include <cstdio>
#include <cstdlib>
using namespace std;



vector <int> sub_vector(int b, int e, vector <int>& f){
    vector <int> r(e-b);
    rep(i,0,e-b){
        r[i]=f[i+b];
    }
    return r;
}
int binary(int s, int ee, int e, vector <int>& curr){
    int start=s, end = ee;
    while(start!=end-1)
    {
        int middle = (start+end)/2;
        vector <int> sub = sub_vector(middle,e, curr);
        int see = Query(sub);
        if(sub.size()==see)
            end=middle;
        else
            start=middle;
    }
    return start;
}
vector <bool> visited;
vector <vector <int> > verti;
vector <pair <int, int> > graph;
void dfs(int p){
    vector <int> ch = {0,0,0};
    if(graph[p].first!=-1&&graph[p].second!=-1){
        return ;
    }
    rep(i,0,3){
        rep(j,i+1,3){
            if(i==j)continue;
            vector <int> ctry = {p, verti[p][i], verti[p][j]};
            if(Query(ctry)==2){
                ch[i]++;
                ch[j]++;
            }
        }
    }
    rep(i,0,3){
        if(ch[i]==2){
            graph[p].second = verti[p][i];
            graph[verti[p][i]].first = p;
            dfs(verti[p][i]);
        }
    }
    return ;
}
void Solve(int N) {
    int n=N*2;
    vector <vector <int> > v(4);
    verti.resize(n+1);
    visited.assign(n+1,0);
    graph.assign(n+1,{-1,-1});
    rep(i,1, n+1){
        vector <int> curr;
        bool flag = false;
        vector<int> which= {-1,-1,-1,-1};
        rep(j,0,4){
            curr = v[j];
            curr.push_back(i);
            int check = Query(curr);
            if(check==curr.size()){
                which[j]=curr.size();
                continue;
            }
          	int start = 0, end = curr.size();
            while(check!=curr.size()){
                int remov = binary(start, end, curr.size(), curr);
                verti[i].push_back(curr[remov]);
                verti[curr[remov]].push_back(i);
              	end = remov;
                curr.erase (curr.begin()+remov);
                check = Query(curr);
            }
        }
        int place = 5, capasity = n+1;
        rep(i,0,4){
            if(which[i]!=-1&& capasity>which[i]){
                place=i;
            }
        }
        v[place].push_back(i);
    }
    // rep(i,0,4){
    //     cout << i << ": ";
    //     rep(j,0,v[i].size()){
    //         cout << v[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    // rep(i,1,n+1){
    //     cout << i << ": ";
    //     rep(j,0,verti[i].size()){
    //         cout << verti[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    rep(i,1,n+1){
        if(visited[i])continue;
        if(verti[i].size()==1){
            //cout << " 1 "<< i  << " " << verti[i][0] << endl;
            Answer(i,verti[i][0]);
            visited[i]=1;
            visited[verti[i][0]]=1;
        } else if(verti[i].size()>1&& graph[i].first!=-1){
            rep(j,0,3){
                if(verti[i][j]!=graph[i].first&& verti[i][j]!=graph[i].second){
                    //cout << " 2 " << i  << " " << verti[i][j] << endl;
                    Answer(i,verti[i][j]);
                    visited[i]=1;
                    visited[verti[i][j]]=1;
                }
            }
        } else if(verti[i].size()>1){
            dfs(i);
            rep(j,0,3){
                if(verti[i][j]!=graph[i].first&& verti[i][j]!=graph[i].second){
                    //cout << " 3 " << i << " " << verti[i][j] << endl;
                    Answer(i,verti[i][j]);
                    visited[i]=1;
                    visited[verti[i][j]]=1;
                }
            }
        }
    }
}

Compilation message

chameleon.cpp: In function 'int binary(int, int, int, std::vector<int>&)':
chameleon.cpp:33:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(sub.size()==see)
            ~~~~~~~~~~^~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:81:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(check==curr.size()){
                ~~~~~^~~~~~~~~~~~~
chameleon.cpp:86:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(check!=curr.size()){
                   ~~~~~^~~~~~~~~~~~~
chameleon.cpp:75:14: warning: unused variable 'flag' [-Wunused-variable]
         bool flag = false;
              ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 28 ms 384 KB Output is correct
4 Correct 27 ms 256 KB Output is correct
5 Correct 28 ms 384 KB Output is correct
6 Correct 27 ms 384 KB Output is correct
7 Correct 27 ms 512 KB Output is correct
8 Correct 27 ms 384 KB Output is correct
9 Correct 28 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 28 ms 384 KB Output is correct
4 Correct 27 ms 256 KB Output is correct
5 Correct 28 ms 384 KB Output is correct
6 Correct 27 ms 384 KB Output is correct
7 Correct 27 ms 512 KB Output is correct
8 Correct 27 ms 384 KB Output is correct
9 Correct 28 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 7 ms 384 KB Output is correct
19 Correct 6 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 8 ms 512 KB Output is correct
27 Correct 7 ms 512 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Incorrect 62 ms 504 KB Wrong Answer [3]
31 Halted 0 ms 0 KB -