oj.uz

답안 #634531

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
634531 2022-08-24T14:26:16 Z LittleCube Flights (JOI22_flights) C++17
32 / 100
 314 ms 2224 KB 
#include "Ali.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

int N, pre[10005], dis[10005];

pii decode(ll p, int N)
{
	ll acc = 0;
	for(int i = 0; i < N; i++)
		if(acc <= p && p < acc + N - i - 1)
			return pii(i, i + 1 + p - acc);
		else 
			acc += N - i - 1;
	assert(0);
}

vector<int> E[10005];

void dfs(int u)
{
	for(int v : E[u])
		if(pre[u] != v)
		{
			pre[v] = u;
			dis[v] = dis[u] + 1;
			dfs(v);
		}
}



void Init(int n, vector<int> U, vector<int> V) 
{
	N = n;
	for(int i = 0; i < N; i++)
		E[i].clear();
	for(int i = 0; i < N - 1; i++)
	{
		E[U[i]].emplace_back(V[i]);
		E[V[i]].emplace_back(U[i]);
	}
	for(int i = 0; i < N; i++)
		SetID(i, i);
	
	dfs(0);
	cerr << "Init\n";
}

int dist(int x, int y)
{
	int ans = 0;
	for(;x != y; ans++)
	{
		if(dis[x] < dis[y])
			swap(x, y);
		x = pre[x];
	}
	return ans;
}

string SendA(string S) 
{
	ll r = 0;
	for(char c : S)
		r = (r << 1) + (c == '1');

	string res;

	for(int q = 0; (q << 20) + r <= N * (N - 1) / 2; q++)
	{
		cerr << "Sending " << q << " with remainder " << r;
		auto [x, y] = decode((q << 20) + r, N);
		cerr << ", which is vertex " << x << ", " << y << '\n';
		int d = dist(x, y);
		for(int p = 13; p >= 0; p--)
			res.push_back(((d >> p) & 1) ? '1' : '0');
	}	
	cerr << "Ali: Sent\n";
	return res;
}
#include "Benjamin.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

ll encode(int x, int y, int N)
{
	ll acc = 0;
	for(int i = 0; i < x; i++)
		acc += N - i - 1;
	return acc + y - x - 1;
}

ll q, r;

string SendB(int N, int X, int Y) 
{
	if(X > Y)
		swap(X, Y);
	
	q = encode(X, Y, N) >> 20;
	r = encode(X, Y, N) - (q << 20);
	
	string res;
	for(int i = 19; i >= 0; i--)
		res.push_back(((r >> i) & 1) ? '1' : '0');
	cerr << "Ben: Sent\n";
	return res;
}

int Answer(string T) 
{
	int ans = 0;
	for(int i = 0; i <= 13; i++)
		ans = (ans << 1) + (T[q * 14 + i] == '1');
	cerr << "Answer returned\n";
	return ans;
}

Compilation message

grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 656 KB Output is correct
2 Correct 2 ms 656 KB Output is correct
3 Correct 2 ms 656 KB Output is correct
4 Correct 2 ms 740 KB Output is correct
5 Correct 2 ms 656 KB Output is correct
6 Correct 6 ms 1288 KB Output is correct
7 Correct 6 ms 1288 KB Output is correct
8 Correct 7 ms 1288 KB Output is correct
9 Correct 7 ms 1288 KB Output is correct
10 Correct 9 ms 1416 KB Output is correct
11 Correct 5 ms 1172 KB Output is correct
12 Correct 7 ms 1324 KB Output is correct
13 Correct 8 ms 1384 KB Output is correct
14 Correct 6 ms 1288 KB Output is correct
15 Correct 6 ms 2012 KB Output is correct
16 Correct 5 ms 1504 KB Output is correct

Subtask #2
17.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 668 KB Output is correct
2 Partially correct 51 ms 2056 KB Output is partially correct
3 Correct 6 ms 744 KB Output is correct
4 Partially correct 279 ms 1528 KB Output is partially correct
5 Partially correct 239 ms 1572 KB Output is partially correct
6 Partially correct 248 ms 1664 KB Output is partially correct
7 Partially correct 226 ms 2224 KB Output is partially correct
8 Partially correct 243 ms 1588 KB Output is partially correct
9 Partially correct 228 ms 1840 KB Output is partially correct
10 Partially correct 231 ms 1928 KB Output is partially correct
11 Partially correct 251 ms 1600 KB Output is partially correct
12 Partially correct 27 ms 1224 KB Output is partially correct
13 Partially correct 145 ms 1508 KB Output is partially correct
14 Partially correct 147 ms 1428 KB Output is partially correct
15 Correct 6 ms 784 KB Output is correct
16 Partially correct 256 ms 2208 KB Output is partially correct
17 Partially correct 242 ms 2192 KB Output is partially correct
18 Partially correct 247 ms 2028 KB Output is partially correct
19 Partially correct 218 ms 2004 KB Output is partially correct
20 Partially correct 159 ms 1820 KB Output is partially correct
21 Partially correct 225 ms 2024 KB Output is partially correct
22 Partially correct 219 ms 1584 KB Output is partially correct
23 Partially correct 226 ms 1576 KB Output is partially correct
24 Partially correct 207 ms 1660 KB Output is partially correct
25 Partially correct 208 ms 1580 KB Output is partially correct
26 Partially correct 202 ms 1568 KB Output is partially correct
27 Partially correct 218 ms 1588 KB Output is partially correct
28 Partially correct 209 ms 1492 KB Output is partially correct
29 Partially correct 285 ms 1688 KB Output is partially correct
30 Partially correct 314 ms 1492 KB Output is partially correct
31 Partially correct 224 ms 1600 KB Output is partially correct
32 Partially correct 278 ms 1540 KB Output is partially correct
33 Partially correct 210 ms 1596 KB Output is partially correct
34 Partially correct 251 ms 1688 KB Output is partially correct
35 Partially correct 233 ms 1492 KB Output is partially correct
36 Partially correct 218 ms 1564 KB Output is partially correct
37 Partially correct 242 ms 1608 KB Output is partially correct
38 Partially correct 244 ms 1528 KB Output is partially correct
39 Partially correct 39 ms 1456 KB Output is partially correct
40 Partially correct 264 ms 2028 KB Output is partially correct