oj.uz

Submission #581997

# Submission time Handle Problem Language Result Execution time Memory
581997 2022-06-23T09:21:32 Z sysia Chameleon's Love (JOI20_chameleon) C++17
40 / 100
 18 ms 336 KB 
//Sylwia Sapkowska
#include <bits/stdc++.h>
#include "chameleon.h"
#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif


void Solve(int n){
	vector<vector<int>>diff(2*n+1);
	for (int i = 1; i<=2*n; i++){
		for (int j = 1; j<=2*n; j++){
			if (i == j) continue;
			int x = Query({i, j});
			if (x == 1)	diff[i].emplace_back(j);
		}
	}
	vector<pair<int, int>>ans;
	vector<int>G(2*n+1, -1), who(2*n+1, -1);
	// debug(diff);
	vector<bool>vis(2*n+1, 0);
	for (int i = 1; i<=2*n; i++){
		if ((int)diff[i].size() == 1 && !vis[diff[i][0]]){
			ans.emplace_back(i, diff[i][0]);
			vis[i] = 1;
			vis[diff[i][0]] = 1;
		} else if (diff[i].size() == 3) {
			vector<int>curr;
			for (int j = 0; j<3; j++){
				curr.clear();
				for (int k = 0; k<3; k++){
					if (k == j) continue;
					curr.emplace_back(diff[i][k]);
				}
				curr.emplace_back(i);
				if (Query(curr) == 1){
					G[i] = diff[i][j];
					who[diff[i][j]] = i;
				}
			}
			
		}
	}
	// debug(ans);
	// debug(G);
	// debug(who);
	for (int i = 1; i<=2*n; i++){
		if (vis[i]) continue;
		if ((int)diff[i].size() == 3){
			for (int j = 0; j<3; j++){
				if (diff[i][j] == G[i] || diff[i][j] == who[i]){
					continue;
				}
				ans.emplace_back(i, diff[i][j]);
				vis[i] = 1;
				vis[diff[i][j]] = 1;
			}
		}
	}
	// debug(ans);
	for (auto [a, b]:ans) Answer(a, b);
}

Subtask #1
0 / 4.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 18 ms 336 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 208 KB Output is correct
2 Correct 2 ms 208 KB Output is correct
3 Incorrect 17 ms 336 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -