oj.uz

답안 #527622

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
527622 2022-02-17T20:35:38 Z LucaDantas Alternating Current (BOI18_alternating) C++17
0 / 100
 26 ms 3524 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 3e5+10;

int pref[maxn];
int mx = 0, ini_mx = 0, n, m;

struct Wire {
	int l, r, id;
	int sz() const { return r >= l ? r - l + 1 : r + (n - l + 1); }
	bool operator<(const Wire& o) const {
		if(l == o.l) return this->sz() > o.sz();
		if((l >= ini_mx) == (o.l >= ini_mx)) return l < o.l; // retorno o que tem o menor l já que eles são da mesma metade
		return l > o.l; // já que eles são de metades diferentes eu retorno o que tiver na metade maior
	}
} wr[maxn];

int pai[maxn];

int main() {
	scanf("%d %d", &n, &m);
	for(int i = 0; i < m; i++) {
		scanf("%d %d", &wr[i].l, &wr[i].r); wr[i].id = i;
		if(wr[i].l <= wr[i].r) {
			pref[wr[i].l]++;
			pref[wr[i].r+1]--;
		} else {
			pref[wr[i].l]++;
			pref[1]++;
			pref[wr[i].r+1]--;
		}
		
		if(wr[i].sz() > mx) {
			mx = wr[i].sz();
			ini_mx = wr[i].l;
		}
	}

	for(int i = 1; i <= n; i++) {
		pref[i] += pref[i-1];
		if(pref[i] < 2) return puts("impossible"), 0;
	}

	sort(wr, wr+m);

	bool virou = 0;
	int fim = 0, aberto = -1;

	vector<Wire> brabos;

	memset(pai, -1, sizeof pai);
	for(int i = 0; i < m; i++) {
		auto [l, r, id] = wr[i];
		if(make_pair(virou, fim) < make_pair(r < l || l < ini_mx, r)) {
			brabos.push_back(wr[i]);
			aberto = id;
			fim = r;
			virou |= r < l || l < ini_mx;
		} else pai[id] = aberto;
	}

	puts("BRABOS: ");
	printf("Size: %ld\n", brabos.size());
	for(Wire x : brabos)
		printf("(%d %d %d) ", x.l, x.r, x.id);
	puts("");

	vector<int> ans(m);

	auto print = [&]() {
		for(int i = 0; i < m; i++)
			printf("%d", ans[i]);
		puts("");
		exit(0);
	};

	if(brabos[0].sz() == n) {
		ans[brabos[0].id] = 1;
		print();
	}

	if(brabos.size() % 2 == 0) {
		for(int i = 0; i < brabos.size(); i++)
			ans[brabos[i].id] = i&1;
		
		for(int i = 0; i < m; i++)
			if(pai[i] != -1) ans[i] = 1^ans[pai[i]];

		print();
	}

	brabos.push_back(brabos.front());

	int r_a = -1;
	for(int i = 0; i < brabos.size(); i++) {
		auto [l, r, id] = brabos[i];
		if(r_a != -1) {
			bool tem = pref[r_a] >= 3;
			static int cnt = 0;
			for(int j = l; j != (r_a-1)%n + 1; j = (j%n)+1)
				tem &= pref[j] >= 3;
 
			if(l == ((r_a)%n+1) || tem) {
				brabos.pop_back();
				if(i == brabos.size()) i = 0;
 
				auto nxt = [&](int x) { return x%brabos.size()+1; };
 
				ans[brabos[i].id] = 1;
				for(int k = i+1, opa = 0; k != i; k = nxt(k), opa ^= 1)
					ans[brabos[k].id] = opa;
		
				for(int i = 0; i < m; i++)
					if(pai[i] != -1) ans[i] = 1^ans[pai[i]];

				print();
			}
 
		}
		r_a = r;
	}
	puts("impossible");
}

Compilation message

alternating.cpp: In function 'int main()':
alternating.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Wire>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for(int i = 0; i < brabos.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~
alternating.cpp:96:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Wire>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  for(int i = 0; i < brabos.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~
alternating.cpp:106:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Wire>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     if(i == brabos.size()) i = 0;
      |        ~~^~~~~~~~~~~~~~~~
alternating.cpp:100:15: warning: unused variable 'cnt' [-Wunused-variable]
  100 |    static int cnt = 0;
      |               ^~~
alternating.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
alternating.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |   scanf("%d %d", &wr[i].l, &wr[i].r); wr[i].id = i;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
alternating.cpp: At global scope:
alternating.cpp:100:15: warning: 'cnt' defined but not used [-Wunused-variable]
  100 |    static int cnt = 0;
      |               ^~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1356 KB BRABOS: is not a string of length exactly 15
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1356 KB BRABOS: is not a string of length exactly 15
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1356 KB BRABOS: is not a string of length exactly 15
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 3524 KB BRABOS: is not a string of length exactly 100000
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1356 KB BRABOS: is not a string of length exactly 15
2 Halted 0 ms 0 KB -