oj.uz

Submission #68840

# Submission time Handle Problem Language Result Execution time Memory
68840 2018-08-18T18:13:43 Z reality None (JOI16_memory2) C++17
100 / 100
 4 ms 764 KB 
#include "Memory2_lib.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define vii vector < pii >
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}

const int N = 128;

int G[N][N];

int get(int x,int y) {
	assert(x != y);
	if (x > y)
		swap(x,y);
	if (G[x][y] == -1)
		G[x][y] = Flip(x,y);
	return G[x][y];
}

int ans[N];

vi pos[N];

void Set(int index,int val) {
	ans[index] = val;
	pos[val].pb(index);
}

void Solve(int T, int NN) {
	int n = NN;
	memset(G,-1,sizeof(G));
	if (n == 1) {
		Answer(0,1,0);
		return;
	}
	int A = 0,B = 1,C = 2;
	for (int i = 3;i < n + n;++i) {
		vi p = {A,B,C,i};
		int who = -1;
		for (int i = 0;i < 4;++i) {
			vi v;
			for (int j = 0;j < 4;++j)
				if (i != j)
					v.pb(get(p[i],p[j]));
			sort(all(v));
			if (v[0] == v.back()) {
				who = i;
				break;
			}
		}
		assert(who != -1);
		Set(p[who],get(p[who == 0],p[who]));
		p.erase(p.begin() + who);
		A = p[0];
		B = p[1];
		C = p[2];
	}
	vi ps;
	for (int i = 0;i < n;++i)
		for (int j = pos[i].size();j < 2;++j)
			ps.pb(i);
	// Last three are harder than the others.........
	int ab = get(A,B);
	int bc = get(B,C);
	int ac = get(A,C);
	if (ps[0] == ps[1])
		swap(ps[0],ps[2]);
	if (ps[1] == ps[2]) {
		if (ac == bc && ac == ab) {
			int ind = pos[ps[0]][0];
			if (get(ind,A) == ps[0]) {
				Set(A,ps[0]);
				Set(B,ps[1]);
				Set(C,ps[2]);
			} else 
			if (get(ind,B) == ps[0]) {
				Set(B,ps[0]);
				Set(A,ps[1]);
				Set(C,ps[2]);
			} else {
				Set(C,ps[0]);
				Set(A,ps[1]);
				Set(B,ps[2]);
			}
		} else {
			if (ab == ps[1]) {
				Set(A,ps[1]);
				Set(B,ps[2]);
				Set(C,ps[0]);
			} else
			if (ac == ps[1]) {
				Set(A,ps[1]);
				Set(C,ps[2]);
				Set(B,ps[0]);
			} else {
				Set(A,ps[0]);
				Set(B,ps[1]);
				Set(C,ps[2]);
			}
		}
	} else {
		if (ab == ac) {
			Set(A,ab);
			int w = ps[0] + ps[1] + ps[2] - ab - bc;
			if (get(B,pos[w][0]) == w) {
				Set(B,w);
				Set(C,bc);
			} else {
				Set(C,w);
				Set(B,bc);
			}
		} else
		if (ab == bc) {
			Set(B,ab);
			int w = ps[0] + ps[1] + ps[2] - ab - ac;
			if (get(A,pos[w][0]) == w) {
				Set(A,w);
				Set(C,ac);
			} else {
				Set(C,w);
				Set(A,ac);
			}
		} else {
			Set(C,bc);
			int w = ps[0] + ps[1] + ps[2] - ac - bc;
			if (get(A,pos[w][0]) == w) {
				Set(A,w);
				Set(B,ab);
			} else {
				Set(B,w);
				Set(A,ab);
			}
		}
	}
	for (int i = 0;i < n;++i)
		assert(pos[i].size() == 2);
	for (int i = 0;i < n;++i)
		Answer(pos[i][0],pos[i][1],i);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
50.0 / 50.0

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

Subtask #3
40.0 / 40.0

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