oj.uz

Submission #708273

# Submission time Handle Problem Language Result Execution time Memory
708273 2023-03-11T13:42:16 Z aggrovector None (JOI16_memory2) C++17
60 / 100
 1 ms 304 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);
			}
			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==1) {
		for (i=0;i<N;i++) {
			cnt[i]=0;
		}
		for (i=0;i<N*2;i++) {
			if (ans[i]==-1) {
				x=i;
				continue;
			}
			cnt[ans[i]]++;
		}
		for (i=0;i<N*2;i++) {
			if (cnt[i]<2) {
				ans[x]=i;
			}
		}
	}
	else 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:51: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]
   51 |    for (i=0;i<w.size();i++) {
      |             ~^~~~~~~~~
memory2.cpp:105: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]
  105 |   for (i=0;i<v.size();i++) {
      |            ~^~~~~~~~~
memory2.cpp:119: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]
  119 |   for (i=0;i<v.size();i++) {
      |            ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 304 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Wrong Answer[3]
2 Halted 0 ms 0 KB -