제출 #88087

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
88087		MAMBA	Teoretičar (COCI18_teoreticar)	C++17	130 / 130	10855 ms	167348 KiB

teoreticar

#ifdef _MSC_VER
#define __builtin_popcount (int)__popcnt
#define __builtin_popcountll (int)__popcnt64
#define __builtin_clz (int)__lzcnt
#define $ system("pause")
#else
#define $
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> point;

#define MOD ll(1e9 + 7)
#define MAXN int(5e5 + 20)
#define lg 17
#define inf int(2e9 + 100)

#define rep(i, j, k) for (int i = j; i < k; i++)
#define for_all(x) x.begin(), x.end()
#define lid id << 1
#define rid id << 1 | 1
#define lch l, mid, lid
#define rch mid, r, rid
#define pb push_back
#define X first
#define Y second
#define re real()
#define im imag()

template <typename S, typename T>
inline ostream &operator<<(ostream &out, const pair<S, T> &p)
{
	return out << "( " << p.X << " , " << p.Y << " )";
}
template <typename S>
inline ostream &operator<<(ostream &out, const vector<S> &p)
{
	for (auto &e : p) out << e << ' '; return out;
}
template <typename T, typename S> inline T
smin(T &a, const S &b) { return a > b ? a = b : a; }
template <typename T, typename S> inline T
smax(T &a, const S &b) { return a < b ? a = b : a; }
inline double dot(const point l, const point r) { return l.re * r.re + l.im * r.im; }
inline double cross(const point l, const point r) { return l.re * r.im - l.im * r.re; }
ll po(ll v, ll u) { return u ? (po(v * v % MOD, u >> 1) * (u & 1 ? v : 1) % MOD) : 1; }
inline void add(ll &l, const ll &r) { l = (l + r) % MOD; }
ll gcd(ll v, ll u) { return u ? gcd(u, v % u) : v; }

int L, R, m, yal[MAXN], color[MAXN], supervec;
pii sar[MAXN * 2];
vector<int> adj[MAXN];
bool mark[MAXN * 2];
void tour(int v, int level) {
	while (!adj[v].empty()) {
		int e = adj[v].back();
		adj[v].pop_back();
		if (mark[e]) continue;
		mark[e] = true;
		if (v >= L && e < m) color[e] ^= (1 << level);
		tour(sar[e].X + sar[e].Y - v, level);
	}
	return;
}

void solve(int l , int r, int level = 0) {
	rep(i, l, r) {
		adj[sar[yal[i]].Y].pb(yal[i]);
		adj[sar[yal[i]].X].pb(yal[i]);
	}
	int Z = m;
	int mx = 0;
	rep(i, l, r) {
		int v = sar[yal[i]].X;
		int u = sar[yal[i]].Y;
		smax(mx, adj[v].size());
		smax(mx, adj[u].size());
		if ((int)adj[v].size() & 1) {
			adj[v].pb(Z);
			adj[supervec].pb(Z);
			sar[Z++] = { v , supervec };
		}
		if ((int)adj[u].size() & 1) {
			adj[u].pb(Z);
			adj[supervec].pb(Z);
			sar[Z++] = { u , supervec };
		}
	}
	if (mx < 2) {
		rep(i, l, r) {
			adj[sar[yal[i]].Y].clear();
			adj[sar[yal[i]].X].clear();
		}
		adj[supervec].clear();
		return;
	}
	rep(i, l, r)
		if (!adj[sar[yal[i]].X].empty())
			tour(sar[yal[i]].X, level);
	//
	rep(i, l, r) mark[yal[i]] = false;
	rep(i, m, Z) mark[i] = false;
	int lptr = l, rptr = r - 1;
	while (lptr != rptr) {
		if (color[yal[lptr]] & (1 << level))
			swap(yal[lptr], yal[rptr]), rptr--;
		else lptr++;
	}
	if (color[yal[lptr]] & (1 << level)) lptr--;
	lptr++;
	solve(l, lptr, level + 1);
	solve(lptr, r, level + 1);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> L >> R >> m;
	supervec = L + R;
	rep(i, 0, m) {
		int u, v;
		cin >> u >> v; u--; v--;
		v += L;
		sar[i] = { u , v };
		yal[i] = i;
	}
	solve(0, m);
	cout << *max_element(color, color + m) + 1 << '\n';
	rep(i, 0, m)
		cout << color[i] + 1 << '\n';
	$;
	return (0);
}

컴파일 시 표준 에러 (stderr) 메시지

teoreticar.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::vector<_Tp>&)':
teoreticar.cpp:47:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (auto &e : p) out << e << ' '; return out;
  ^~~
teoreticar.cpp:47:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (auto &e : p) out << e << ' '; return out;
                                     ^~~~~~
teoreticar.cpp: In instantiation of 'T smax(T&, const S&) [with T = int; S = long unsigned int]':
teoreticar.cpp:85:25:   required from here
teoreticar.cpp:52:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 smax(T &a, const S &b) { return a < b ? a = b : a; }
                                 ~~^~~

• Subtask 1: 13 / 13
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 13 / 13
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13
• Subtask 9: 13 / 13
• Subtask 10: 13 / 13