#include <iostream>
#include <cmath>
#include <math.h>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <queue>
#define M 1000000007
#define pii pair<int, int>
typedef long long ll;
using namespace std;
/*
vector<vector<int>>vec;
vector<bool>visit;
vector<int>w;
vector<pair<int, pii>>dp1;
vector<pair<int, pii>>dp2;
vector<int>pre;
pair<int,pii> max1(pair<int, pii>a1, pair<int, pii>a2,bool v1,bool v2) {
if (a1.first > a2.first)
return a1;
else if (a1.first < a2.first)
return a2;
else {
if (v1 and !v2)
return a1;
if (v2 and !v1)
return a2;
else {
int tmp1 = abs(a1.second.second - a1.second.first);
int tmp2 = abs(a2.second.second - a2.second.first);
if (tmp1 > tmp2)
return a1;
else if (tmp2 > tmp1)
return a2;
else {
if (a1.second.second > a2.second.second) {
return a1;
}
else if (a2.second.second > a1.second.second)
return a2;
else {
if (a1.second.first > a2.second.first) {
return a2;
}
else if (a2.second.first > a1.second.first)
return a1;
else
return a1;
}
}
}
}
}
vector<bool>he;
void dfs(int v) {
visit[v] = true;
for (int i = 0; i < vec[v].size(); i++) {
if (!visit[vec[v][i]]) {
dfs(vec[v][i]);
}
dp2[v] = max1({ dp1[vec[v][i]].first,{w[v],w[v]} }, dp2[v], true, true);
int val2 = abs(w[vec[v][i]] - w[v]) + dp2[vec[v][i]].first;
int val = dp1[vec[v][i]].second.second - dp1[vec[v][i]].second.first;
int val1 = max(dp1[vec[v][i]].second.second, w[v]) - min(dp1[vec[v][i]].second.first, w[v]);
int val3 = dp1[vec[v][i]].first - val + val1;
bool tmp123 = he[v];
if (val1 > val)
he[v] = true;
else
he[v] = false;
if (val3 >= val2) {
pair<int, pii> a1 = max1({ val3,{min(dp1[vec[v][i]].second.first, w[v]),max(dp1[vec[v][i]].second.second, w[v])} }, dp1[v], he[i], tmp123);
if (dp1[v] != a1 )
pre[v] = vec[v][i];
dp1[v] = a1;
}
else {
pair <int, pii>a1 = max1({ val2,{min(w[vec[v][i]],w[i]),max(w[vec[v][i]],w[i])} }, dp1[v], he[i], tmp123);
if (dp1[v] != a1)
pre[v] = vec[v][i];
dp1[v] = a1;
}
}
}
vector<int>sed;
void bfs(int v) {
vector<bool>visit(vec.size());
vector<int>distance1(vec.size());
distance1[v] = 0;
for (int i = 0; i < vec.size(); i++) {
visit[i] = false;
}
queue<int>queue1;
queue1.push(v);
visit[v] = true;
while (queue1.empty() == false) {
sed.push_back(queue1.front());
int cur = queue1.front();
queue1.pop();
for (int i = 0; i < vec[cur].size(); i++) {
if (visit[vec[cur][i]] == false) {
visit[vec[cur][i]] = true;
distance1[vec[cur][i]] = distance1[cur] + 1;
queue1.push(vec[cur][i]);
}
}
}
}
int main() {
ios::sync_with_stdio(false);
int n;
cin >> n;
he.resize(n);
pre.resize(n,-1);
w.resize(n);
for (int i = 0; i < n; i++)
cin >> w[i];
vec.resize(n);
visit.resize(n, false);
vector<int>num(n, 0);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--; v--;
vec[u].push_back(v);
num[u]++;
}
dp1.resize(n, { -1,{-1,-1} });
dp2.resize(n, { -1,{-1,-1} });
for (int i = 0; i < n; i++) {
if (num[i] == 0) {
dp1[i] = { 0,{w[i],w[i]} };
dp2[i] = { 0,{w[i],w[i]} };
visit[i] = true;
}
}
dfs(0);
vector<bool>visit1(n, false);
ll ans = 0;
bfs(0);
for (int i = 0; i < n; i++) {
if (!visit1[sed[i]]) {
ans += dp1[sed[i]].first;
int tmp12 = i;
while (tmp12!=-1) {
visit1[tmp12] = true;
tmp12 = pre[tmp12];
}
}
}
cout << ans;
}*/
/*
int main() {
int n, k;
cin >> n >> k;
multiset<int>set1;
vector<int>vec(n+k);
ll sum = 0;
for (int i = 0; i < n + k; i++) {
cin >> vec[i];
set1.insert(vec[i]);
sum += vec[i];
}
for (int i = 0; i < n + k; i++) {
ll sum1 = sum - vec[i];
set1.erase(set1.find(vec[i]));
auto it = set1.begin();
int a1 = *it;
++it;
int a2 = *it;
int d = a2 - a1;
ll sum2 = (2 * a1 + (n - 1) * d) * n / 2;
if (sum2 == sum1) {
int cnt = 0;
for (int j = 0; j < n + k; j++) {
if (j != i) {
cnt++;
cout << vec[j];
if (cnt != n)
cout << " ";
}
}
break;
}
set1.insert(vec[i]);
}
}*/
/*
#include <map>
vector<int>visit;
int main() {
int n, m, g;
cin >> n >> m >> g;
map<int, set<int>>mp;
vector<int>shor;
vector<pii>gre;
for (int i = 0; i < g; i++) {
int x, y;
cin >> y >> x;
mp[y].insert(x);
shor.push_back(y);
gre.push_back({ y,x });
}
sort(shor.begin(), shor.end());
sort(gre.begin(), gre.end());
int q;
cin >> q;
vector<pii>vec(g);
map<pii, int>con;
for (int i = 0; i < g; i++) {
con[gre[i]] = i;
if (mp[gre[i].first + 1].size() == 0)
vec[i] = { -1, -1 };
else {
auto it = mp[gre[i].first + 1].end();
--it;
if (gre[i].second > * it)
vec[i] = { -1, -1 };
else
vec[i] = { gre[i].first + 1,*mp[gre[i].first + 1].lower_bound(gre[i].second) };
}
}
while (q--) {
int x1, x2, y1, y2;
cin >> y1 >> x1 >> y2 >> x2;
pii st;
if (mp[y1].size() == 0)
st = { -1, -1 };
else {
auto it = mp[y1].end();
--it;
if(x1 > * it)
st = { -1, -1 };
else
st = { y1,*mp[y1].lower_bound(x1) };
}
bool flag = false;
if (y1 == y2 and x1 <= x2)
flag = true;
if (st.first != -1) {
while (!flag) {
if (st.first == y2-1 and st.second <= x2)
flag = true;
else if (vec[con[st]].first == -1)
break;
else if (vec[con[st]].second > x2)
break;
else {
st = vec[con[st]];
}
}
}
if (flag)
cout << "YES";
else
cout << "NO";
cout << endl;
}
}*/
/*
#include "grader.h"
#include <map>
void solve(int n){
map<int, int>his;
set<int>vec;
for (int i = 0; i < n; i++) {
int k = kth(i);
his[k]++;
vec.insert(k);
}
for (auto u : vec) {
if (his[u] >= n / 3)
say_answer(u);
}
say_answer(-1);
}*/
int main() {
int k;
cin >> k;
if (k == 1) {
cout << 2 << " " << 2 << endl;
cout << "rd" << endl << "r.";
}
if (k == 2) {
cout << 2 << " " << 2 << endl;
cout << "Xd" << endl << "r.";
}
if (k == 3) {
cout << 2 << " " << 3 << endl;
cout << "XXd" << endl << "rr.";
}
if (k == 4) {
cout << 2 << " " << 4 << endl;
cout << "XXXd" << endl << "rrr.";
}
if (k == 5) {
cout << 2 << " " << 5 << endl;
cout << "XXXXd" << endl << "rrrr.";
}
if (k == 6) {
cout << 3 << " " << 3 << endl;
cout << "XXd" << endl << "XXd" << endl << "rr.";
}
if (k == 7) {
cout << 3 << " " << 4 << endl;
cout << "XXXd" << endl << "XXdd" << endl << "rrr.";
}
if (k == 8) {
cout << 3 << " " << 5 << endl;
cout << "XXXXd" << endl << "XXddd" << endl << "rrrr.";
}
if (k == 9) {
cout << 4 << " " << 4 << endl;
cout << "XXrd" << endl << "XXXd" << endl <<"Xddd"<< endl << "rrr.";
}
if (k == 10) {
cout << 5 << " " << 4 << endl;
cout << "XXrd" << endl << "XXXd" << endl << "Xddd" << endl << "Xddd" << endl << "rrr.";
}
if (k == 11) {
cout << 4 << " " << 4 << endl;
cout << "XXXd" << endl << "XXXd" << endl << "Xddd" << endl << "rrr.";
}
if (k == 12) {
cout << 5 << " " << 4 << endl;
cout << "XXXd" << endl << "XXXd" << endl << "Xddd" << endl << "Xddd" << endl << "rrr.";
}
if (k == 13) {
cout << 5 << " " << 5 << endl;
cout << "XXrrd" << endl << "XXXdd" << endl << "ddXdd" << endl << "XdXdd" << endl << "rrrr.";
}
if (k == 14) {
cout << 5 << " " << 5 << endl;
cout << "XXrrd" << endl << "XXXdd" << endl << "XdXdd" << endl << "XdXdd" << endl << "rrrr.";
}
if (k == 15) {
cout << 5 << " " << 5 << endl;
cout << "XXXXd" << endl << "XXXrd" << endl << "XdXrd" << endl << "dddrd" << endl << "rrrr.";
}
if (k == 16) {
cout << 5 << " " << 5 << endl;
cout << "XXXXd" << endl << "XXXXd" << endl << "Xdddd" << endl << "ddddd" << endl << "rrrr.";
}
if (k == 17) {
cout << 5 << " " << 5 << endl;
cout << "XXXXd" << endl << "XXXXd" << endl << "Xdddd" << endl << "ddddd" << endl << "rrrr.";
}
if (k == 18) {
cout << 5 << " " << 5 << endl;
cout << "XXXXd" << endl << "XXXXd" << endl << "ddXrd" << endl << "ddddd" << endl << "rrrr.";
}
if (k == 19) {
cout << 5 << " " << 5 << endl;
cout << "XXXXd" << endl << "XXXXd" << endl << "dddXd" << endl << "ddddd" << endl << "rrrr.";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Correct! Your size: 3 |
| 2 |
Correct |
0 ms |
204 KB |
Correct! Your size: 4 |
| 3 |
Correct |
0 ms |
204 KB |
Correct! Your size: 5 |
| 4 |
Correct |
0 ms |
204 KB |
Correct! Your size: 3 |
| 5 |
Correct |
0 ms |
204 KB |
Correct! Your size: 4 |
| 6 |
Correct |
1 ms |
204 KB |
Correct! Your size: 5 |
| 7 |
Correct |
0 ms |
204 KB |
Correct! Your size: 5 |
| 8 |
Correct |
0 ms |
204 KB |
Correct! Your size: 5 |
| 9 |
Correct |
0 ms |
204 KB |
Correct! Your size: 5 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
