oj.uz

Submission #112089

# Submission time Handle Problem Language Result Execution time Memory
112089 2019-05-17T11:38:19 Z mechfrog88 None (JOI16_memory2) C++14
100 / 100
 3 ms 384 KB 
#include "Memory2_lib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void Solve(int T, int N){
	vector <ll> num(N*2,-1);
	vector <ll> arr(N*2);
	srand(time(0));
	for (int z=0;z<N*2;z++){
		arr[z] = z;
	}
	random_shuffle(arr.begin(),arr.end());
	ll p=-1,q=-1,r=-1,a=-1,b=-1,c=-1;
	while (arr.size() > 4){
		if (p == -1){
			p = arr[rand()%arr.size()];
			while (num[p] != -1 || p==q || p==r){
				p = arr[rand()%arr.size()];
			}
		}
		
		if (q == -1){
			q = arr[rand()%arr.size()];
			while (num[q] != -1 || p==q || q==r){
				q = arr[rand()%arr.size()];
			}
		}

		if (r == -1){
			r = arr[rand()%arr.size()];
			while (num[r] != -1 || r==p || q==r){
				r = arr[rand()%arr.size()];
			}
		}
		if (a == -1) a = Flip(p,q);
		if (b == -1) b = Flip(p,r);
		if (c == -1) c = Flip(q,r);
		if (a == b && b == c && c == a) {
			p=-1;q=-1;r=-1;a=-1;b=-1;c=-1;
			continue;
		}
		if (a == b){
			num[p] = a;
			for (int z=0;z<arr.size();z++){
				if (arr[z] == p){
					arr.erase(arr.begin()+z);
					break;
				}
			}
			p = -1;
			a = -1;
			b = -1;
		}
		else if (b == c){
			num[r] = b;
			for (int z=0;z<arr.size();z++){
				if (arr[z] == r){
					arr.erase(arr.begin()+z);
					break;
				}
			}
			r = -1;
			b = -1;
			c = -1;
		}
		else if (c == a){
			num[q] = c;
			for (int z=0;z<arr.size();z++){
				if (arr[z] == q){
					arr.erase(arr.begin()+z);
					break;
				}
			}
			q = -1;
			c = -1;
			a = -1;
		}
	}
	vector <vector<ll>> d(arr.size(),vector<ll>(arr.size()));
	for (int z=0;z<arr.size();z++){
		for (int x=z+1;x<arr.size();x++){
			d[z][x] = Flip(arr[z],arr[x]);
			d[x][z] = d[z][x];
		}
	}
	ll s = arr.size();
	vector <ll> visited(arr.size(),false);
	ll ca = arr.size();
	while (ca > 1){
		for (int z=0;z<s;z++){
			if (visited[z]) continue;
			ll first = 0;
			ll count = 1;
			while (visited[first] || first == z){
				first++;
			}
			for (int x=0;x<s;x++){
				if (z == x) continue;
				if (visited[x]) continue;
				if (d[z][x] == d[z][first])count++;
			}
			if (count == ca){
				num[arr[z]] = d[z][first];
				ca--;
				visited[z] = true;
				break;
			}
		}
	}
	ll last;
	vector<vector<ll>> ans(N);
	for (int z=0;z<N*2;z++){
		if (num[z] == -1) {
			last = z; continue;
		}
		ans[num[z]].push_back(z);
	} 
	for (int z=0;z<N;z++){
		if (ans[z].size() == 1){
			ans[z].push_back(last);
		}
		Answer(ans[z][0],ans[z][1],z);
	}
	return;
}

Compilation message

memory2.cpp: In function 'void Solve(int, int)':
memory2.cpp:45:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int z=0;z<arr.size();z++){
                 ~^~~~~~~~~~~
memory2.cpp:57:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int z=0;z<arr.size();z++){
                 ~^~~~~~~~~~~
memory2.cpp:69:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int z=0;z<arr.size();z++){
                 ~^~~~~~~~~~~
memory2.cpp:81:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int z=0;z<arr.size();z++){
               ~^~~~~~~~~~~
memory2.cpp:82:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int x=z+1;x<arr.size();x++){
                  ~^~~~~~~~~~~
memory2.cpp:111:5: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
  ll last;
     ^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
50.0 / 50.0

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

Subtask #3
40.0 / 40.0

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