oj.uz

Submission #1009006

# Submission time Handle Problem Language Result Execution time Memory
1009006 2024-06-27T07:52:22 Z emptypringlescan Chameleon's Love (JOI20_chameleon) C++17
44 / 100
 23 ms 596 KB 
    #include <bits/stdc++.h>
    using namespace std;
    #include "chameleon.h"
    vector<pair<int,int> > eds,adj[1005];
    vector<int> st,v;
    unordered_set<int> disj[2];
    int vis[1005];
    void change(int x, int g){
    	if(disj[g].find(x)==disj[g].end()) return;
    	disj[g].erase(x);
    	disj[g^1].insert(x);
    	vis[x]=1;
    	for(auto i:adj[x]){
    		if(!vis[i.first]) change(i.first,g^1);
    	}
    }
    void Solve(int n){
    	int x;
    	for(int i=1; i<=2*n; i++){
    		vector<int> ds;
    		for(int j:disj[0]) ds.push_back(j);
    		int lo=0,hi=(int)ds.size(),mid;
    		while(lo<hi){
    			mid=(lo+hi)/2;
    			v.clear();
    			v.push_back(i);
    			for(int j=lo; j<=mid; j++) v.push_back(ds[j]);
    			x=Query(v);
    			if(x<(int)v.size()) hi=mid;
    			else lo=mid+1;
    		}
    		if((int)ds.size()>lo){
    			eds.push_back({ds[lo],i});
    			adj[i].push_back({ds[lo],eds.size()-1});
    			adj[ds[lo]].push_back({i,eds.size()-1});
    			st.push_back(0);
    		}
    		
    		lo++,hi=(int)ds.size();
    		while(lo<hi){
    			mid=(lo+hi)/2;
    			v.clear();
    			v.push_back(i);
    			for(int j=lo; j<=mid; j++) v.push_back(ds[j]);
    			x=Query(v);
    			if(x<(int)v.size()) hi=mid;
    			else lo=mid+1;
    		}
    		if((int)ds.size()>lo){
    			eds.push_back({ds[lo],i});
    			adj[i].push_back({ds[lo],eds.size()-1});
    			adj[ds[lo]].push_back({i,eds.size()-1});
    			st.push_back(0);
    		}
    		
    		lo++,hi=(int)ds.size();
    		while(lo<hi){
    			mid=(lo+hi)/2;
    			v.clear();
    			v.push_back(i);
    			for(int j=lo; j<=mid; j++) v.push_back(ds[j]);
    			x=Query(v);
    			if(x<(int)v.size()) hi=mid;
    			else lo=mid+1;
    		}
    		if((int)ds.size()>lo){
    			eds.push_back({ds[lo],i});
    			adj[i].push_back({ds[lo],eds.size()-1});
    			adj[ds[lo]].push_back({i,eds.size()-1});
    			st.push_back(0);
    		}
    		
    		ds.clear();
    		for(int j:disj[1]) ds.push_back(j);
    		lo=0,hi=(int)ds.size();
    		while(lo<hi){
    			mid=(lo+hi)/2;
    			v.clear();
    			v.push_back(i);
    			for(int j=lo; j<=mid; j++) v.push_back(ds[j]);
    			x=Query(v);
    			if(x<(int)v.size()) hi=mid;
    			else lo=mid+1;
    		}
    		if((int)ds.size()>lo){
    			for(int j=0; j<=500; j++) vis[j]=0;
    			change(ds[lo],1);
    			eds.push_back({ds[lo],i});
    			adj[i].push_back({ds[lo],eds.size()-1});
    			adj[ds[lo]].push_back({i,eds.size()-1});
    			st.push_back(0);
    		}
    		
    		lo++,hi=(int)ds.size();
    		while(lo<hi){
    			mid=(lo+hi)/2;
    			v.clear();
    			v.push_back(i);
    			for(int j=lo; j<=mid; j++) v.push_back(ds[j]);
    			x=Query(v);
    			if(x<(int)v.size()) hi=mid;
    			else lo=mid+1;
    		}
    		if((int)ds.size()>lo){
    			for(int j=0; j<=500; j++) vis[j]=0;
    			change(ds[lo],1);
    			eds.push_back({ds[lo],i});
    			adj[i].push_back({ds[lo],eds.size()-1});
    			adj[ds[lo]].push_back({i,eds.size()-1});
    			st.push_back(0);
    		}
    		
    		lo++,hi=(int)ds.size();
    		while(lo<hi){
    			mid=(lo+hi)/2;
    			v.clear();
    			v.push_back(i);
    			for(int j=lo; j<=mid; j++) v.push_back(ds[j]);
    			x=Query(v);
    			if(x<(int)v.size()) hi=mid;
    			else lo=mid+1;
    		}
    		if((int)ds.size()>lo){
    			for(int j=0; j<=500; j++) vis[j]=0;
    			change(ds[lo],1);
    			eds.push_back({ds[lo],i});
    			adj[i].push_back({ds[lo],eds.size()-1});
    			adj[ds[lo]].push_back({i,eds.size()-1});
    			st.push_back(0);
    		}
    		
    		disj[1].insert(i);
    	}
    	for(int i=1; i<=2*n; i++){
    		if((int)adj[i].size()==1) continue;
    		assert((int)adj[i].size()==3);
    		int a=Query({i,adj[i][0].first,adj[i][1].first});
    		int b=Query({i,adj[i][0].first,adj[i][2].first});
    		int c=Query({i,adj[i][1].first,adj[i][2].first});
    		if(a==1) st[adj[i][2].second]=1;
    		if(b==1) st[adj[i][1].second]=1;
    		if(c==1) st[adj[i][0].second]=1;
    	}
    	for(int i=0; i<(int)eds.size(); i++){
    		if(st[i]==0) Answer(eds[i].first,eds[i].second);
    	}
    }

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 17 ms 504 KB Output is correct
4 Correct 17 ms 344 KB Output is correct
5 Correct 17 ms 344 KB Output is correct
6 Correct 18 ms 528 KB Output is correct
7 Correct 23 ms 344 KB Output is correct
8 Correct 18 ms 344 KB Output is correct
9 Correct 20 ms 548 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 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 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 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 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 352 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 352 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 596 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 0 ms 348 KB Output is correct
3 Incorrect 21 ms 540 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 17 ms 504 KB Output is correct
4 Correct 17 ms 344 KB Output is correct
5 Correct 17 ms 344 KB Output is correct
6 Correct 18 ms 528 KB Output is correct
7 Correct 23 ms 344 KB Output is correct
8 Correct 18 ms 344 KB Output is correct
9 Correct 20 ms 548 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 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 1 ms 344 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 1 ms 352 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 0 ms 352 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 596 KB Output is correct
28 Correct 0 ms 344 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Incorrect 21 ms 540 KB Wrong Answer [3]
31 Halted 0 ms 0 KB -