| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 313928 | georgerapeanu | Chameleon's Love (JOI20_chameleon) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "chameleon.h"
#include <vector>
#include <cstdio>
#include <cassert>
using namespace std;
vector<int> graph[1005];
vector<int> groups[2];
bool viz[1005];
void dfs(int nod,int lvl){
viz[nod] = 1;
groups[lvl].push_back(nod);
for(auto it:graph[nod]){
if(viz[it]){
continue;;
}
dfs(it,lvl ^ 1);
}
}
void make_groups(int pas){
for(int i = 1;i <= pas;i++){
viz[i] = false;
}
groups[0].clear();
groups[1].clear();
for(int i = 1;i <= pas;i++){
if(viz[i] == 0){
dfs(i,0);
}
}
}
int ans[1005];
int lover[1005];
vector<int> reunite(vector<int> a,vector<int> b){
vector<int> ans;
for(auto it:a)ans.push_back(it);
for(auto it:b)ans.push_back(it);
return ans;
}
vector<int> prefix(vector<int> a,int ind){
vector<int> ans;
for(int i = 0;i <= ind;i++){
ans.push_back(a[i]);
}
return ans;
}
vector<int> del(vector<int> a,int val){
vector<int> ans;
for(auto it:a){
if(it == val){
continue;
}
ans.push_back(it);
}
return ans;
}
int my_query(const vector<int> &v){
return Query(v);
}
void Solve(int n) {
for(int i = 1;i <= 2 * n;i++){
make_groups(i - 1);
for(int k = 0;k < 2;k++){
while(my_query(reunite({i},groups[k])) != reunite({i},groups[k]).size()){
int st = -1,dr = (int)groups[k].size() - 1;
while(dr - st > 1){
int mid = (st + dr) / 2;
if(my_query(reunite({i},prefix(groups[k],mid))) == mid + 2){
st = mid;
}
else{
dr = mid;
}
}
graph[i].push_back(groups[k][dr]);
graph[groups[k][dr]].push_back(i);
groups[k] = del(groups[k],groups[k][dr]);
}
}
}
for(int i = 1;i <= 2 * n;i++){
if(graph[i].size() == 1){
continue;
}
int loves = 0;
for(loves = 0;loves < (int)graph[i].size();loves++){
if(graph[i][(loves + 1) % 3] == graph[i][(loves + 2) % 3]){
loves = (loves + 1) % 3;
break;
}
if(my_query({i,graph[i][(loves + 1) % 3],graph[i][(loves + 2) % 3]}) == 1){
break;
}
}
lover[i] = graph[i][loves];
}
for(int i = 1;i <= 2 * n;i++){
if(ans[i] == 0){
for(auto it:graph[i]){
if(lover[i] == it || lover[it] == i){
continue;
}
ans[i] = it;
ans[it] = i;
Answer(i,it);
break;
}
}
}
}
#include "chameleon.h"
#include <cstdio>
#include <cstdlib>
namespace {
using std::exit;
using std::fprintf;
using std::printf;
using std::scanf;
constexpr int Q_MAX = 20'000;
constexpr int N_MAX = 500;
int N;
int Y[N_MAX * 2 + 1], C[N_MAX * 2 + 1], L[N_MAX * 2 + 1];
int query_count = 0;
int answer_count = 0;
bool finishes[N_MAX * 2 + 1];
void WrongAnswer(int code) {
printf("Wrong Answer [%d]\n", code);
exit(0);
}
} // namespace
int Query(const std::vector<int> &p) {
if (++query_count > Q_MAX) WrongAnswer(3);
bool presents[N_MAX * 2 + 1];
for (int i = 1; i <= N * 2; ++i) presents[i] = false;
for (const int k : p) {
if (k <= 0 || k > N * 2) WrongAnswer(1);
if (presents[k]) WrongAnswer(2);
presents[k] = true;
}
bool colors[N_MAX + 1];
for (int j = 1; j <= N; ++j) colors[j] = false;
int color_count = 0;
for (int i = 1; i <= N * 2; ++i) {
if (!presents[i]) continue;
const int color = presents[L[i]] ? C[L[i]] : C[i];
if (!colors[color]) {
++color_count;
colors[color] = true;
}
}
return color_count;
}
void Answer(int a, int b) {
++answer_count;
if (a <= 0 || a > N * 2) WrongAnswer(4);
if (b <= 0 || b > N * 2) WrongAnswer(4);
if (finishes[a]) WrongAnswer(5);
finishes[a] = true;
if (finishes[b]) WrongAnswer(5);
finishes[b] = true;
if (C[a] != C[b]) WrongAnswer(6);
}
int main() {
if (scanf("%d", &N) != 1) {
fprintf(stderr, "Error while reading input.\n");
exit(1);
}
for (int i = 1; i <= N * 2; ++i) {
if (scanf("%d", &Y[i]) != 1) {
fprintf(stderr, "Error while reading input.\n");
exit(1);
}
}
for (int i = 1; i <= N * 2; ++i) {
if (scanf("%d", &C[i]) != 1) {
fprintf(stderr, "Error while reading input.\n");
exit(1);
}
}
for (int i = 1; i <= N * 2; ++i) {
if (scanf("%d", &L[i]) != 1) {
fprintf(stderr, "Error while reading input.\n");
exit(1);
}
}
for (int i = 1; i <= N * 2; ++i) finishes[i] = false;
Solve(N);
if (answer_count != N) WrongAnswer(7);
printf("Accepted: %d\n", query_count);
return 0;
}