Submission #527621

#	Time	Username	Problem	Language	Result	Execution time	Memory
527621		LucaDantas	Alternating Current (BOI18_alternating)	C++17	19 / 100	44 ms	5296 KiB

alternating

    #include <bits/stdc++.h>
    using namespace std;
     
    constexpr int maxn = 2e5+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];
     
    	for(int i = n+1; i <= 2*n; i++) {
    		pref[i] = pref[i-n];
    		if(pref[i] < 2) return puts("impossible"), 0;
    	}
     
    	sort(wr, wr+m);
     
    	for(int i = 0; i < m; i++)
    		if(wr[i].l < ini_mx) wr[i].l += n, wr[i].r += n, assert(wr[i].l <= wr[i].r);
    		else if(wr[i].r < ini_mx) assert(wr[i].r < wr[i].l), wr[i].r += n;
     
    	int fim = 0, aberto = 0;
     
    	vector<Wire> brabos;
     	memset(pai, -1, sizeof pai);
    	for(int i = 0; i < m; i++) {
    		auto [l, r, id] = wr[i];
    		if(r > fim) brabos.push_back(wr[i]), aberto = id, fim = r;
    		else pai[id] = aberto;
    	}
     
    	vector<int> ans(m);
    	if(((brabos.size() & 1) ^ 1) || brabos.size() == 1) {
    		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]];
    		
    		for(int i = 0; i < m; i++)
    			printf("%d", ans[i]);
    		puts("");
    		return 0;
    	}
     
    	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]];
    				
    				for(int i = 0; i < m; i++)
    					printf("%d", ans[i]);
    				puts("");
    				return 0;
    			}
     
    		}
    		r_a = r;
    	}
    	puts("impossible");
    }

Compilation message (stderr)

alternating.cpp: In function 'int main()':
alternating.cpp:66:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Wire>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |       for(int i = 0; i < brabos.size(); i++)
      |                      ~~^~~~~~~~~~~~~~~
alternating.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Wire>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |      for(int i = 0; i < brabos.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
alternating.cpp:91:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Wire>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         if(i == brabos.size()) i = 0;
      |            ~~^~~~~~~~~~~~~~~~
alternating.cpp:85:19: warning: unused variable 'cnt' [-Wunused-variable]
   85 |        static int cnt = 0;
      |                   ^~~
alternating.cpp:22:11: 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:12: 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:85:19: warning: 'cnt' defined but not used [-Wunused-variable]
   85 |        static int cnt = 0;
      |                   ^~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 19 / 19
• Subtask 5: 0 / 26