oj.uz

Submission #236550

# Submission time Handle Problem Language Result Execution time Memory
236550 2020-06-02T13:12:20 Z Knps4422 Meetings (JOI19_meetings) C++14
29 / 100
 2000 ms 1020 KB 
//#pragma optimization_level 3
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordset;
*/
#include "meetings.h"
#define fr first
#define sc second
#define vec vector
#define pb push_back
#define pii pair<int, int>
#define forn(x,y) for(int x = 1 ; x <= (int)y ; ++x)
#define all(x) (x).begin(),(x).end()
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
 
using namespace std;
 
typedef long long ll;
typedef unsigned int uint;
typedef complex<int> point;
const int nmax = 100005;
const ll linf = 1e18;
const ll mod = 998244353;
const int inf = INT_MAX;

vec < pii > eds;
int find_center(vec <int> &asd){
	if(asd.size() <= 10)return asd[0];
	vec<int> cnt(asd.size());
	int tries = 1;
	while(tries --){
		int m = asd.size();
		int a, b, c;
		a = asd[rand()%m];
		b = asd[rand()%m];
		while(b == a) b = asd[rand()%m];
		c = asd[rand()%m];
		while(c == b || c == a)c = asd[rand()%m];
		// a,b,c - random din asd
		int p = Query(a,b,c);
		cnt[ lower_bound(all(asd),p) - asd.begin()]++;
	}
	int mx = 0;
	for(int i = 0; i < cnt.size() ; i++){
		if(cnt[mx] < cnt[i])mx = i;
	}
	cnt.clear();
	return asd[mx];
}
int find_center2(vec <int> &asd){
	srand(time(NULL));
	if(asd.size() < 10)return asd[0];
	int guess = asd[0];
	random_shuffle(all(asd));
	for(int i = 1 ; i < (int) asd.size()/5 ; i+= 2){
		if(asd[i] != guess && asd[i+1] != guess){
			guess = Query(guess,asd[i],asd[i+1]);	
		}
	}
	return guess;
}
void solves(vec <int> &tb){
	if(tb.size() == 1)return ;
	int A = find_center2(tb);
	int B = tb[0];
	if(B == A)B = tb[1];
	for(int i : tb){
		if(i != A && i != B && Query(A,B,i) == i) B = i;
	}
	eds.pb({A,B});
	vec < int > left;
	vec < int > right;
	for(int  i : tb){
		if(i != A && i != B){
			if(Query(A,B,i) == A){
				left.pb(i);
			}else{
				right.pb(i);
			}
		}
	}
	left.pb(A);
	sort(all(left));	
	solves(left);
	left.clear();
	right.pb(B);
	sort(all(right));
	solves(right);
	right.clear();
}


void Solve(int n){
	vec < int > asd;
	for(int i= 0; i <n ; i++)asd.pb(i);
	solves(asd);
	for(pii ed : eds){
		Bridge(min(ed.fr,ed.sc),max(ed.fr,ed.sc));
	}
	asd.clear();
}

/*
int main(){
	fast;
	
}
*/

Compilation message

meetings.cpp: In function 'int find_center(std::vector<int>&)':
meetings.cpp:50:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < cnt.size() ; i++){
                 ~~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 20 ms 384 KB Output is correct
28 Correct 21 ms 384 KB Output is correct
29 Correct 23 ms 384 KB Output is correct
30 Correct 21 ms 384 KB Output is correct
31 Correct 20 ms 384 KB Output is correct
32 Correct 24 ms 504 KB Output is correct
33 Correct 32 ms 512 KB Output is correct
34 Correct 36 ms 384 KB Output is correct
35 Correct 35 ms 384 KB Output is correct
36 Correct 22 ms 384 KB Output is correct
37 Correct 20 ms 384 KB Output is correct
38 Correct 25 ms 384 KB Output is correct
39 Correct 22 ms 384 KB Output is correct

Subtask #4
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 1491 ms 780 KB Output is correct
2 Correct 1627 ms 748 KB Output is correct
3 Correct 1701 ms 888 KB Output is correct
4 Correct 1826 ms 760 KB Output is correct
5 Correct 1465 ms 760 KB Output is correct
6 Correct 1274 ms 864 KB Output is correct
7 Correct 1467 ms 632 KB Output is correct
8 Correct 1669 ms 888 KB Output is correct
9 Correct 1687 ms 772 KB Output is correct
10 Correct 1488 ms 636 KB Output is correct
11 Correct 1848 ms 964 KB Output is correct
12 Correct 1341 ms 760 KB Output is correct
13 Correct 1328 ms 796 KB Output is correct
14 Correct 1299 ms 888 KB Output is correct
15 Correct 1350 ms 888 KB Output is correct
16 Correct 1493 ms 632 KB Output is correct
17 Correct 1525 ms 760 KB Output is correct
18 Correct 1562 ms 884 KB Output is correct
19 Correct 1584 ms 1020 KB Output is correct
20 Correct 1655 ms 756 KB Output is correct
21 Correct 1725 ms 864 KB Output is correct
22 Correct 1713 ms 760 KB Output is correct
23 Correct 1675 ms 632 KB Output is correct
24 Correct 1752 ms 888 KB Output is correct
25 Correct 1798 ms 760 KB Output is correct
26 Execution timed out 2073 ms 672 KB Time limit exceeded
27 Halted 0 ms 0 KB -