oj.uz

Submission #236648

# Submission time Handle Problem Language Result Execution time Memory
236648 2020-06-02T17:10:20 Z MvC Meetings (JOI19_meetings) C++14
29 / 100
 1622 ms 1716 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#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;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
 
typedef long long ll;
typedef unsigned int uint;
typedef complex<int> point;
const int nmax = 2005;
const ll linf = 1e18;
const ll mod = 998244353;
const int inf = INT_MAX;
 
vec < pii > eds;
int A,n,vz[nmax],u;
vector<int>vc[nmax];
/*int Query(int x,int y,int z)
{
	cout<<"Q "<<x<<" "<<y<<" "<<z<<endl;
	int rs;
	cin>>rs;
	return rs;
}*/
bool cmp(int x,int y)
{
	u++;
	return Query(A,x,y)==x;
}
void solves(vec <int> tb){
	if(tb.size() == 1)return ;
	if(tb.size()==2)
	{
		eds.pb({tb[0],tb[1]});
		return;
	}
	srand(time(0));
	for(int i:tb)vc[i].clear(),vz[i]=0;
	int m=tb.size(),B;
	A=B=0;
	while(B == A)B = tb[rand()%m],A=tb[rand()%m];
	vector<int>pth;
	for(int i : tb){
		if(i != A && i != B && Query(A,B,i) == i) u++,pth.pb(i);
	}
	pth.pb(B);
	sort(all(pth),cmp);
	reverse(all(pth));
	pth.pb(A);
	for(int i=1;i<pth.size();i++)eds.pb({pth[i-1],pth[i]});
	for(int i=0;i<pth.size();i++)vz[pth[i]]=1,vc[pth[i]].pb(pth[i]);
	for(int i : tb){
		if(!vz[i])
		{
			vc[Query(A,B,i)].pb(i);
			u++;
		}
	}
	for(int i=0;i<pth.size();i++)
	{
		solves(vc[pth[i]]);
	}
}
void Solve(int n)
{
	vec < int > asd;
	for(int i= 0; i <n ;i++)asd.pb(i);
	solves(asd);
	assert(u<=30000);
	for(pii ed : eds){
		Bridge(min(ed.fr,ed.sc),max(ed.fr,ed.sc));
	}
}
/*int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n;
	
	return 0;
}*/

Compilation message

meetings.cpp: In function 'void solves(std::vector<int>)':
meetings.cpp:62:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<pth.size();i++)eds.pb({pth[i-1],pth[i]});
              ~^~~~~~~~~~~
meetings.cpp:63:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<pth.size();i++)vz[pth[i]]=1,vc[pth[i]].pb(pth[i]);
              ~^~~~~~~~~~~
meetings.cpp:71:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<pth.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 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 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 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 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 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 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 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 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 512 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 512 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 512 KB Output is correct
21 Correct 5 ms 512 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 512 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 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 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 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 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 512 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 512 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 512 KB Output is correct
21 Correct 5 ms 512 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 512 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 15 ms 512 KB Output is correct
28 Correct 12 ms 512 KB Output is correct
29 Correct 13 ms 512 KB Output is correct
30 Correct 11 ms 512 KB Output is correct
31 Correct 13 ms 512 KB Output is correct
32 Correct 18 ms 640 KB Output is correct
33 Correct 22 ms 512 KB Output is correct
34 Correct 24 ms 512 KB Output is correct
35 Correct 21 ms 512 KB Output is correct
36 Correct 15 ms 512 KB Output is correct
37 Correct 14 ms 512 KB Output is correct
38 Correct 14 ms 512 KB Output is correct
39 Correct 16 ms 512 KB Output is correct

Subtask #4
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 861 ms 888 KB Output is correct
2 Correct 835 ms 760 KB Output is correct
3 Correct 886 ms 1016 KB Output is correct
4 Correct 942 ms 804 KB Output is correct
5 Correct 912 ms 888 KB Output is correct
6 Correct 646 ms 760 KB Output is correct
7 Correct 864 ms 796 KB Output is correct
8 Correct 874 ms 920 KB Output is correct
9 Correct 1030 ms 1016 KB Output is correct
10 Correct 829 ms 760 KB Output is correct
11 Correct 840 ms 760 KB Output is correct
12 Correct 634 ms 992 KB Output is correct
13 Correct 648 ms 1016 KB Output is correct
14 Correct 514 ms 1016 KB Output is correct
15 Correct 661 ms 760 KB Output is correct
16 Correct 679 ms 820 KB Output is correct
17 Correct 847 ms 888 KB Output is correct
18 Correct 598 ms 1016 KB Output is correct
19 Correct 506 ms 1016 KB Output is correct
20 Correct 822 ms 888 KB Output is correct
21 Correct 792 ms 1084 KB Output is correct
22 Correct 783 ms 916 KB Output is correct
23 Correct 768 ms 888 KB Output is correct
24 Correct 1098 ms 1016 KB Output is correct
25 Correct 688 ms 888 KB Output is correct
26 Correct 835 ms 1032 KB Output is correct
27 Correct 926 ms 888 KB Output is correct
28 Correct 915 ms 888 KB Output is correct
29 Correct 816 ms 888 KB Output is correct
30 Correct 781 ms 1156 KB Output is correct
31 Correct 879 ms 1148 KB Output is correct
32 Correct 1060 ms 1016 KB Output is correct
33 Runtime error 1622 ms 1716 KB Execution killed with signal 11 (could be triggered by violating memory limits)