oj.uz

Submission #222913

# Submission time Handle Problem Language Result Execution time Memory
222913 2020-04-14T10:44:05 Z quocnguyen1012 Chameleon's Love (JOI20_chameleon) C++14
0 / 100
 5 ms 384 KB 
#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
 
bool sex[1005];
vector <int> v[1005];
 
vector <int> Left, Right;
vector <int> cand[1005];
 
bool isCandidate(int x, int y, vector <int> v, int val){
    vector <int> q;
    if(val != -1) q.push_back(val);
    for(int i = x; i <= y ; ++i) q.push_back(v[i]);
 
    return Query(q) - q.size();
}
 
bool find_candidates(int i, vector <int> v){
    if(!v.empty()){
        while(isCandidate(0, v.size() - 1, v, i)){
            if(v.size() == 1){
                cand[i].push_back(v[0]);
                cand[v[0]].push_back(i);
 
                v.pop_back();
                break ;
            }
 
            int st = 1, dr = v.size();
            while(st <= dr){
                int mij = (st + dr) / 2;
                if(isCandidate(st - 1, mij - 1, v, i)) dr = mij - 1;
                else st = mij + 1;
            }
 
            cand[i].push_back(v[st - 1]);
            cand[v[st - 1]].push_back(i);
 
            swap(v[st - 1], v[v.size() - 1]);
            v.pop_back();
 
            if(v.empty() || cand[i].size() == 3) break ;
        }
    }
}
 
bool viz[1005];
void color(int nod){
    viz[nod] = 1;
    for(auto it : cand[nod]){
        if(viz[it]) continue ;
        sex[it] = 1 - sex[nod];
        color(it);
    }
}
 
bool match[1005][1005];
bool found[1005];
 
void Solve(int n){
    for(int i = 2; i <= 2 * n ; ++i){
        for(int j = 1; j < i ; ++j) viz[j] = 0;
 
        sex[i - 1] = 0;
        color(i - 1);
 
        ///we find all the chameleons on the left
        Left.clear();
        for(int j = 1; j < i ; ++j)
            if(cand[j].size() < 3) Left.push_back(j);
 
        find_candidates(i, Left);
    }
 
    for(int i = 1; i <= 2 * n ; ++i){
        if(found[i]) continue ;
        if(cand[i].size() == 1){
            found[i] = found[cand[i][0]] = true;
            Answer(i, cand[i][0]);
            continue ;
        }
 
        vector <int> v;
        bool ok = false;
        for(auto x : cand[i]){
            for(auto y : cand[i]){
                if(x >= y) continue ;
                v.clear();
                v.push_back(x);
                v.push_back(y);
                v.push_back(i);
                if(Query(v) == 1){
                    match[i][x] = 1;
                    match[i][y] = 1;
                    ok = true;
                    break ;
                }
            }
            if(ok) break ;
        }
    }
 
    for(int i = 1; i <= 2 * n ; ++i){
        if(found[i]) continue ;
        for(int j = 1; j <= 2 * n ; ++j){
            if(found[j]) continue ;
            if(match[i][j] && match[j][i]){
                found[i] = found[j] = true;
                Answer(i, j);
            }
        }
    }
}

Compilation message

chameleon.cpp: In function 'bool find_candidates(int, std::vector<int>)':
chameleon.cpp:46:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -