Submission #708268

# Submission time Handle Problem Language Result Execution time Memory
708268 2023-03-11T13:36:47 Z aggrovector None (JOI16_memory2) C++17
0 / 100
1 ms 300 KB
#include <bits/stdc++.h>
using namespace std;
long long x,y,i,j,ans[105],f,n,cnt[55],xx[5],maxv,maxi;
vector<pair<long long,long long>> w;
vector<long long> v;
bool flag;

int Flip(int I, int J);
void Answer(int I, int J, int X);

void Solve(int T, int N) {
	for (i=0;i<N*2;i++) {
		ans[i]=-1;
	}
	n=N*2;
	while(n>3) {
		for (i=0;i<N;i++) {
			cnt[i]=0;
		}
		for (i=0;i<N*2;i++) {
			if (ans[i]==-1) {
				f=i;
				break;
			}
		}
		w.clear();
		for (i=f+1;i<N*2;i++) {
			if (ans[i]==-1) {
				x=Flip(f,i);
				w.push_back(make_pair(i,x));
				cnt[x]++;
				if (cnt[x]>=3) {
					break;
				}
			}
		}
		if (cnt[x]>=3) {
			ans[f]=x;
			n--;
			for (i=0;i<w.size();i++) {
				if (w[i].second<x) {
					ans[w[i].first]=w[i].second;
					n--;
				}
			}
		}
		else {
			for (i=0;i<w.size();i++) {
				x=max(x,w[i].second);
			}
			ans[f]=x;
			n--;
			for (i=0;i<w.size();i++) {
				// if (w[i].second<x) {
					ans[w[i].first]=w[i].second;
					n--;
				// }
			}
		}
		// for (i=0;i<w.size();i++) {
		// 	cout << w[i].first << ' ' << w[i].second << endl;
		// }
		// for (i=0;i<N*2;i++) {
		// 	cout << ans[i] << ' ';
		// }
		// cout << endl;
		// cout << endl;
	}
	maxv=0;
	for (i=0;i<N*2;i++) {
		if (maxv<ans[i]) {
			maxv=ans[i];
			maxi=i;
		}
		if (ans[i]==-1) {
			v.push_back(i);
		}
	}
	flag=true;
	// for (i=0;i<N*2;i++) {
	// 	cout << ans[i] << ' ';
	// }
	// cout << endl;
	// for (i=0;i<v.size();i++) {
	// 	cout << v[i] << ' ';
	// }
	// cout << endl;
	// cout << maxi << ' ' << maxv << endl;
	if (n==2) {
		for (i=0;i<v.size();i++) {
			xx[i]=Flip(maxi,v[i]);
			if (xx[i]<maxv) {
				ans[v[i]]=xx[i];
			}
			else if (maxv==N-2) {
				ans[v[i]]=N-1;
			}
			else { //max==n-1
				ans[v[i]]=N-1;
			}
		}
	}
	else {
		for (i=0;i<v.size();i++) {
			xx[i]=Flip(maxi,v[i]);
			if (xx[i]<maxv) {
				ans[v[i]]=xx[i];
			}
			else if (maxv==N-2) {
				flag=false;
			}
			else { //max==N-1
				ans[v[i]]=N-1;
			}
		}
		if (!flag) {
			xx[0]=Flip(v[0],v[1]);
			xx[1]=Flip(v[0],v[2]);
			xx[2]=Flip(v[1],v[2]);
			// cout << xx[0] << ' ' << xx[1] << ' ' << xx[2] << endl;
			if (xx[0]==N-1) {
				ans[v[0]]=N-1;
				ans[v[1]]=N-1;
				ans[v[2]]=xx[1];
			}
			else if (xx[1]==N-1) {
				ans[v[0]]=N-1;
				ans[v[1]]=xx[0];
				ans[v[2]]=N-1;
			}
			else if (xx[2]==N-1) {
				ans[v[0]]=xx[0];
				ans[v[1]]=N-1;
				ans[v[2]]=N-1;
			}
		}
	}
	// for (i=0;i<N*2;i++) {
	// 	cout << ans[i] << ' ';
	// }
	for (i=0;i<N*2;i++) {
		for (j=i+1;j<N*2;j++) {
			if (ans[i]==ans[j]) {
				Answer(i,j,ans[i]);
			}
		}
	}
	return;
}

Compilation message

memory2.cpp: In function 'void Solve(int, int)':
memory2.cpp:40:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |    for (i=0;i<w.size();i++) {
      |             ~^~~~~~~~~
memory2.cpp:48:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |    for (i=0;i<w.size();i++) {
      |             ~^~~~~~~~~
memory2.cpp:53:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |    for (i=0;i<w.size();i++) {
      |             ~^~~~~~~~~
memory2.cpp:90:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |   for (i=0;i<v.size();i++) {
      |            ~^~~~~~~~~
memory2.cpp:104:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   for (i=0;i<v.size();i++) {
      |            ~^~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Wrong Answer[3]
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Wrong Answer[3]
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 300 KB Wrong Answer[3]
2 Halted 0 ms 0 KB -