Submission #1049529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049529		vjudge1	Comparing Plants (IOI20_plants)	C++17	0 / 100	1862 ms	6672 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")
#define endl '\n'
#define db double
#define ll __int128
//#define int long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;

const int Max = 1e4 + 7, Inf = 1e9 + 7;

struct ABI
{
	vector <int> tree; 

	void update(int i, int v)
	{	i++;
		for(i; i < (int) tree.size(); i += (i & -i))
			tree[i] += v; 
	}

	int sum(int i)
	{
		int ans = 0; 
		for(i; i > 0; i-= (i & -i))
			ans += tree[i]; 
		return ans; 
	}

	int query(int l, int r)
	{	l++; r++; 
		if(l <= 1) return sum(r); 
		else return sum(r) - sum(l-1); 
	}

	ABI(int n)
	{
		tree.assign(n + 1, 0); 
	}
};  

vector <vector<int>> v; 
vector <int> pass;

void init(int k, std::vector<int> r) 
{
	int n = r.size(); k--;
	pass.clear(); v.clear();
	v.assign(n+1, vector <int> ()); 
	pass.assign(n+1, 0); 

	_for(i, n) r[i] = k - r[i]; 
	
	ABI St(2*n+7); vector <int> p(2*n+7); 

	bool can = true;

	while (can)
	{
		can = false;
		for(int i = 0; i < n; i++) if(p[i] == 0)
		{	
			//cerr << i << " " << r[i] << " " << St.query(i, i+k) << endl; 
			if(k - St.query(i, i + k) == r[i]){
				St.update(i, 1); St.update(i+n, 1);
				p[i] = 1;
				for(int j = i+1; j <= i+k; j++) if(p[j%n] == 0) {
					v[i].push_back(j % n); 
				} else{
					v[j % n].push_back(i); 
				}
				can = true; 
			}
		}
	}
	
	/*for(int i = 0; i < n; i++){
		cerr << "I: " << i << " -> "; 
		for(auto& u : v[i]) {
			cerr << u << " "; 
		}cerr << endl;
	}*/

	return;
}

int find(int node, int x){
	if(node == x) return 1;  
	if(pass[node]) return 0;
	pass[node] = 1; 
	int can = 0; 
	for(auto&u : v[node]){
		can = can | find(u, x); 
	}
	return can; 
}

int cmp(int a, int b){
	for(auto& u : pass) u = 0; 
	return find(a, b); 
}

int compare_plants(int x, int y) {
	if(cmp(x, y)) return 1; 
	if(cmp(y, x)) return -1; 
	return 0;
}

Compilation message (stderr)

plants.cpp: In member function 'void ABI::update(int, int)':
plants.cpp:28:7: warning: statement has no effect [-Wunused-value]
   28 |   for(i; i < (int) tree.size(); i += (i & -i))
      |       ^
plants.cpp: In member function 'int ABI::sum(int)':
plants.cpp:35:7: warning: statement has no effect [-Wunused-value]
   35 |   for(i; i > 0; i-= (i & -i))
      |       ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25