// link: http://codeforces.com/contest/491/problem/B
/****************************************************************
▄█ █▄ ▄████████ ▄████████ ▄█ ▀█████████▄
███ ███ ███ ███ ███ ███ ███ ███ ███
███ ███ ███ ███ ███ █▀ ███ ███ ███
▄███▄▄▄▄███▄▄ ███ ███ ███ ███ ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀ ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
███ ███ ███ ███ ███ ███ ███ ██▄
███ ███ ███ ███ ▄█ ███ ███ ███ ███
███ █▀ ███ █▀ ▄████████▀ █▀ ▄█████████▀
****************************************************************/
#include<bits/stdc++.h>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;
template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
output<<"[ ";
if(SZ(v))
{
output<<v[0];
}
FOR(i, 1, SZ(v))
{
output<<", "<<v[i];
}
output<<" ]";
return output;
}
template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
output<<"( "<<p.fr<<", "<<p.sc<<" )";
return output;
}
template<typename T>
ostream& operator,(ostream& output, T x)
{
output<<x<<" ";
return output;
}
struct ASDF{
ASDF& operator,(int &a) {
sf("%d", &a);
return *this;
}
ASDF& operator,(long int &a){
sf("%ld", &a);
return *this;
}
ASDF& operator,(long long int &a){
sf("%lld", &a);
return *this;
}
ASDF& operator,(char &c){
sf("%c", &c);
return *this;
}
ASDF& operator,(double &d){
sf("%lf", &d);
return *this;
}
template<typename T>
ASDF& operator,(T &a){
cin>>a;
return *this;
}
}asdf;
//Header ends here
#define INF (1LL<<34)
ll N, M;
ll C, R;
ll x, y;
ll maxA = -INF, maxB = -INF, maxC = -INF, minD = INF;
ll minDist = INF;
int minID = -1;
ll dist(ll x, ll y)
{
ll ret = -INF;
ret = max(ret, maxA - (x+y));
ret = max(ret, maxB - (x-y));
ret = max(ret, maxC - (y-x));
ret = max(ret, (x+y) - minD);
return ret;
}
void init()
{
}
int main()
{
//dump(minDist);
init();
sf("%lld %lld", &N, &M);
sf("%d", &C);
loop(i, C)
{
sf("%lld %lld", &x, &y);
maxA = max(maxA, x+y);
maxB = max(maxB, x-y);
maxC = max(maxC, y-x);
minD = min(minD, x+y);
}
sf("%d", &C);
loop(i, C)
{
sf("%lld %lld", &x, &y);
ll d = dist(x, y);
//dump(d);
if(d < minDist)
{
minDist = d;
minID = i + 1;
}
}
pf("%lld\n%d", minDist, minID);
return 0;
}
Category Archives: CodeForces
D. Hydra (codeforces)
0
//link: http://codeforces.com/contest/244/problem/D
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define dump(x) cout<<#x<<" = "<<x<<endl
using namespace std;
#define take(args...) asdf,args
#define debug(args...) asdfg,args; cout<<endl
struct ASDF{
ASDF& operator,(int &a) {
sf("%d", &a);
return *this;
}
ASDF& operator,(long int &a){
sf("%ld", &a);
return *this;
}
ASDF& operator,(long long int &a){
sf("%lld", &a);
return *this;
}
ASDF& operator,(char &c){
sf("%c", &c);
return *this;
}
ASDF& operator,(double &d){
sf("%lf", &d);
return *this;
}
template<typename T>
ASDF& operator,(T &a){
cin>>a;
return *this;
}
}asdf;
struct ASDFG{
template<typename T>
ASDFG& operator,(vector<T> &v){
pf("[");
cout<<v[0];
FOR(i, 1, SZ(v)){
cout<<", "<<v[i];
}
pf("]");
return *this;
}
template<typename T>
ASDFG& operator,(T x) {
cout<<x<<" ";
return *this;
}
}asdfg;
//Header ends here
#define MAXX 100004
int deg[MAXX];
vector<paii> edges;
int h, t;
vector<int>graph[MAXX];
int isAchived[MAXX];
int isValid(int u, int v)
{
if(deg[u] < h+1 || deg[v] < t+1 )
{
return 0;
}
loop(i, SZ(graph[u]))
{
isAchived[ graph[u][i] ]++;
}
int duplicate = 0;
loop(i, SZ(graph[v]))
{
if(isAchived[ graph[v][i] ])
{
duplicate++;
isAchived[graph[v][i] ]++;
}
}
if(deg[u] + deg[v] - duplicate - 2 >= h+t)
{
return 1;
}
else
{
loop(i, SZ(graph[u])) isAchived[ graph[u][i] ] = 0;
return 0;
}
}
void generateSolution(int u, int v)
{
vector<int>v1, v2, com;
loop(i, SZ(graph[u]))
{
if(graph[u][i] == v) continue;
if(isAchived[ graph[u][i] ] == 1 )
{
v1.pb( graph[u][i] );
}
else
{
com.pb(graph[u][i]);
}
}
loop(i, SZ(graph[v]))
{
if(graph[v][i] == u) continue;
if( isAchived[ graph[v][i] ] == 0 )
{
v2.pb(graph[v][i]);
}
}
int pos = 0;
while(SZ(v1) < h)
{
v1.pb(com[pos++]);
}
while(SZ(v2) < t)
{
v2.pb(com[pos++]);
}
pf("YES\n");
pf("%d %d\n", u, v);
pf("%d", v1[0]);
FOR(i,1,h)
{
pf(" %d", v1[i]);
}
pf("\n");
pf("%d", v2[0]);
FOR(i,1,t)
{
pf(" %d", v2[i]);
}
pf("\n");
}
int main()
{
int n, m, u, v;
take(n, m, h, t);
loop(i, m)
{
take(u, v);
edges.pb(MP(u, v));
deg[u]++; deg[v]++;
graph[u].pb(v); graph[v].pb(u);
}
bool possible = false;
loop(i, m)
{
if(isValid(edges[i].fr, edges[i].sc))
{
possible = 1;
generateSolution(edges[i].fr, edges[i].sc);
break;
}
else if(isValid(edges[i].sc, edges[i].fr))
{
possible=1;
generateSolution(edges[i].sc, edges[i].fr);
break;
}
}
if(!possible) cout<<"NO\n";
}
(CodeForces) C. k-Multiple Free Set
0
/*
user: hasib
link: http://codeforces.com/contest/275/problem/C
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ size()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
#define MAXX 100002
using namespace std;
int number_of_elements;
ll nums[MAXX];
ll k;
int low, high, mid;
bool search(ll n)
{
low = 0;
high = number_of_elements - 1;
while(low <= high)
{
mid = (low+high)/2;
if(nums[mid] == n)
{
break;
}
else if(n < nums[mid])
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
if(low <= high)
return true;
else return false;
}
int main()
{
getint(number_of_elements);
cin>>k;
loop(i, number_of_elements)
{
getint(nums[i]);
}
sort(nums, nums + number_of_elements);
int taken = 0;
ll a;
map<int, bool>visited;
loop(i, number_of_elements)
{
if( visited[nums[i]] == 0 )
{
a = nums[i];
if(search(a*k))
{
if(search(a*k*k))
{
visited[a*k] = 1; //nished
taken++;
}
else
{
visited[a*k] = 1;
taken++;
}
}
else
{
taken++;
}
}
}
cout<<taken<<endl;
return 0;
}
(CodeForces) A. Lights Out
0
/*
user: hasib
link: http://codeforces.com/problemset/problem/275/A
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ size()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
using namespace std;
int xmove[] = {0, 0, 0, -1, 1};
int ymove[] = {0,-1, 1, 0, 0};
int main()
{
int press[3][3];
bool result[3][3];
loop(i, 3)
{
loop(j, 3)
{
cin>>press[i][j];
}
}
int x, y;
mem(result, 1);
loop(i, 3)
{
loop(j, 3)
{
if(press[i][j] % 2 == 1)
{
loop(k, 5)
{
x = i + xmove[k];
y = j + ymove[k];
if(-1 < x && x ❤ && -1 < y && y <3)
{
result[x][y] = !result[x][y];
}
}
}
}
}
loop(i, 3)
{
loop(j, 3)
{
cout<<result[i][j];
}
cout<<endl;
}
return 0;
}
UnLucky Codes 