oj.uz

Submission #1049529

# Submission time Handle Problem Language Result Execution time Memory
1049529 2024-08-08T20:52:40 Z vjudge1 Comparing Plants (IOI20_plants) C++17
0 / 100
 1862 ms 6672 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 29 ms 4188 KB Output is correct
7 Incorrect 618 ms 6672 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.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 Correct 0 ms 344 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 13.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 Correct 0 ms 344 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 1862 ms 4956 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 352 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 29 ms 4188 KB Output is correct
7 Incorrect 618 ms 6672 KB Output isn't correct
8 Halted 0 ms 0 KB -