akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <string>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <float.h>
#include <iomanip>
#include <iostream>
using namespace std;


int main(){

    string S;
    cin >> S;

    smatch results;

    if(regex_match(S,results,regex("(hi)+")))
    {
        cout << "Yes";
    }else{
        cout << "No";
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#define int long long

using namespace std;
using LL = long long;
using P = pair<int, int>;

#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)

#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

const int INF = (int)1e9;
const LL INFL = (LL)1e18;
const int MOD = 1e9 + 7;

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    string s;
    cin >> s;
    LL k;
    cin >> k;

    int num = 0;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == '1') num++;
        else break;
    }

    if(num >= k) cout << 1 << endl;
    else cout << s[num] << endl;
}


Measured memory_bytes: 256
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = list(map(int,readline().split()))

import math
#リスト l の最大公約数
def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = math.gcd(a,l[i])
        if a == 1:
            return 1
    return a

res = gcdlist(lst1)
if res != 1:
    print("not coprime")
    exit()

#nまでの素数のリスト
def eratosthenes(n): #必要な分だけ用意
    if n < 2: #1は素数ではない
        return []
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p: #limit=root(n)
            return prime + data #root(n)まで判定すれば、残りは全て素数であると言える
        prime.append(p)
        data = [e for e in data if e % p != 0] #エラトステネスのふるい
"""素因数分解"""
def get_prime(n):
    b = 2
    fct = []
    while b*b <= n:
        while n % b == 0:
            n //= b
            if not b in fct:
                fct.append(b)
        b += 1
    if n > 1:
        fct.append(n)
    return fct
prime = eratosthenes(10**6)
prime_arr = [0]*10**6
for i in prime:
    prime_arr[i] = 1

for i in lst1:
    if prime_arr[i] == 1:
        prime_arr[i] = -1
    elif prime_arr[i] == -1:
        print("setwise coprime")
        exit()
    else:
        ret = get_prime(i)
        for i in ret:
            if prime_arr[i] == 1:
                prime_arr[i] = -1
            else:
                print("setwise coprime")
                exit()

print("pairwise coprime")

Measured memory_bytes: 202372
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int mod=1e9+7,M=1e6+7;
LL read(){
	LL ans=0,f=1,c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
	while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
	return ans*f;
}
LL n,m,A,B;
LL qmod(LL a,LL b){
	LL ans=1;
	while(b){
		if(b&1) ans=ans*a%mod;
		b>>=1; a=a*a%mod;
	}
	return ans;
}
LL w[M],f[M];
void pre(){
	int mx=2e5; w[0]=1;
	for(int i=1;i<=mx;i++) w[i]=w[i-1]*i%mod;
	f[mx]=qmod(w[mx],mod-2);
	for(int i=mx;i>=1;i--) f[i-1]=f[i]*i%mod;
} 
LL C(LL n,LL m){return w[n]*f[n-m]%mod*f[m]%mod;}
LL F(int x,int y,int nx,int ny){
	int p=nx-x,q=ny-y;
	return C(p+q,q);
}
LL ans;
int main(){
	pre();
	n=read(); m=read(); A=read(); B=read();
	ans=F(1,1,n,m);
	for(int i=1;i<=B;i++){
		int sum=F(1,1,n-A,i)*F(n-A+1,i,n,m)%mod;
		ans=(ans-sum)%mod;
		ans=(ans+mod)%mod;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 5888
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;
typedef pair<int,int> P;

int main(){
    int A[3];
    for(int i=0;i<3;i++){
        cin>>A[i];
    }
    sort(A,A+3);
    int ans=10*A[2]+A[1]+A[0];
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
taka_ta, taka_ko, aoki_ta, aoki_ko = list(map(int, input().split()))

while True:
    aoki_ta -= taka_ko
    if aoki_ta <= 0:
        print('Yes')
        break
    
    taka_ta -= aoki_ko
    if taka_ta <=0 :
        print('No')
        break



Measured memory_bytes: 9100
#include <iostream>
#include <iomanip>
#include <string>
typedef long long ll;
using namespace std;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
#define repi(i, n, init) for (ll i = init; i < (n); i++)

int main()
{
    int n, k;
    string s;
    cin >> n >> s >> k;
    repi(i,n,0){
        if(s[i] != s[k-1])cout << '*';
        else cout << s[i];
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

int main() {
    int x;
    cin>>x;
    if (x>=400 && x<=599){
        cout<<"8";
    }
    else if (x>=600 && x<=799){
        cout<<"7";
    }
    else if (x>=800 && x<=999){
        cout<<"6";
    }
    else if (x>=1000 && x<=1199){
        cout<<"5";
    }
    else if (x>=1200 && x<=1399){
        cout<<"4";
    }
    else if (x>=1400 && x<=1599){
        cout<<"3";
    }
    else if (x>=1600 && x<=1799){
        cout<<"2";
    }
    else if (x>=1800 && x<=1999){
        cout<<"1";
    }
    
    return 0;
    
}

Measured memory_bytes: 3632
#include<iostream>
#include<vector>
using namespace std;

typedef vector<vector<int>> MAP;
int H;

int erase(MAP &field) {
  int point = 0;
  for (int y = 0; y < H; ++y) {
    int l = 2, r = 2;
    int color = field[y][2];
    while (l > 0 and field[y][l-1] == color) l--;
    while (r < 4 and field[y][r+1] == color) r++;
    if (r - l >= 2)
      for (int x = l; x <= r; ++x)
        point += field[y][x], field[y][x] = 0;
  }
  return point;
}

void drop(MAP &field) {
  for (int x = 0; x < 5; ++x) {
    vector<int> v;
    for (int y = H - 1; y >= 0; --y) {
      if (field[y][x] != 0) {
        v.push_back(field[y][x]);
        field[y][x] = 0;
      }
    }
    int y = H - 1;
    for (int color : v) {
      field[y][x] = color;
      --y;
    }
  }
}

int main() {
  while (cin >> H and H) {
    MAP field(H, vector<int>(5));
    for (int y = 0; y < H; ++y)
      for (int x = 0; x < 5; ++x)
        cin >> field[y][x];

    int sum = 0, point = 1;
    while (point > 0) {
      point = erase(field);
      sum += point;
      drop(field);
    }
    cout << sum << endl;
  }
}

Measured memory_bytes: 1216
#include <cstdio>
#include <algorithm>
using namespace std;

bool check(long a, long b, long c, long d) {
    if (a < b || d < b)
        return false;
    if (c >= b)
        return true;
    // c < b <= (a, d)
    a %= b;
    // a < c < b <= d
    long g = __gcd(b, d);
    return a + (b - a - 1) / g * g < c;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        long a, b, c, d;
        scanf("%ld%ld%ld%ld", &a, &b, &c, &d);
        puts(check(a, b, c + 1, d) ? "Yes" : "No");
    }
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 1e9;
// const int MOD = 1e9 + 7;

using P = pair<int, int>;
int main() {
    int N, x;
    cin >> N >> x;
    vector<ll> a(N);
    for (int i = 0; i < N; i++) {
        cin >> a.at(i);
    }
    ll ans = 0;
    for (int i = 0; i < N - 1; i++) {
        int n = a[i] + a[i + 1] - x;
        if (n > 0) {
            ans += n;
            if (n < a[i + 1]) {
                a[i + 1] -= n;
            } else {
                a[i + 1] = 0;
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1024
#include "bits/stdc++.h"

#define debug(x) cout<<#x<<": "<<x<<endl
#define rep(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for (int i=(a);i<=(b);i++)
#define all(a) (a).begin(),(a).end()
using namespace std;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef long long ll;

void solve(){
#ifdef _WIN32
	istream &cin = ifstream("input.txt");
#endif
	int n, q, ans = 0;
	cin >> n;
	VI v(n);
	rep(i, n) cin >> v[i];
	cin >> q;
	VI query(q);
	rep(i, q) cin >> query[i];

	for (int i : query){
		if (find(all(v), i) != v.end())ans++;
	}
	cout << ans << endl;
}


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);


	solve();
	return 0;
}

Measured memory_bytes: 3440
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
	
a1 = a
b1 = b
c1 = c
d1 = d
e1 = e
	
a=(a+9)//10*10
b=(b+9)//10*10
c=(c+9)//10*10
d=(d+9)//10*10
e=(e+9)//10*10

a2 = a-a1
b2 = b-b1
c2 = c-c1
d2 = d-d1
e2 = e-e1

l=[a2,b2,c2,d2,e2]

x = (max(l))

print(a+b+c+d+e-x)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define M 1000000007
#define pi ld(acos(-1.0))
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define Rep(i,n) for(int i=1;i<(int)(n);i++)
#define repp(i,a,b)  for(ll i=a;i<=(ll)(b);i++)
#define Repp(i,a,b)  for(int i=a;i>=(int)(b);i--)
#define cs ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fi first
#define se second
#define ii pair<int,int>
#define bye(x) {cout<<x;return 0;}
typedef long long ll;
typedef long double ld;
using namespace std;

int main() {
    cs
    int n,ans=0;cin>>n;
    vector<int> v(n);
    vector<int> vv(n);
    vector<int> vvv(n-1);
    for(auto &i:v) cin>>i;
    for(auto &i:vv) cin>>i;
    for(auto &i:vvv) cin>>i;
    rep(i,n) {
        ans+=vv[v[i]-1];
        if(i&&v[i]-v[i-1]==1) ans+=vvv[v[i]-2];
    }
    cout<<ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout <<(#x)<<" is "<<(x)<<endl
#define debug cout <<"hi"<<endl
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int MOD=1e9+7;
const int INF32=1<<30;
const ll INF64=1LL<<60;
const int N=1e7;

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  ll n; cin >>n; ll sum=0;
  for(int i=1; i<=n; i++) sum+=(n/i)*(n/i+1)*i/2;
  cout <<sum;
return 0;}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,d;
int A[15][15];
int main(){
	scanf("%d %d",&n,&d);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=d;j++){
			scanf("%d",&A[i][j]);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++){
			ll ret=0;
			for(int k=1;k<=d;k++){
				ret+=(A[i][k]-A[j][k])*(A[i][k]-A[j][k]);
			}
			for(int k=1;k*k<=ret;k++){
				if(ret==k*k)ans++;
			}
		}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>
 
using namespace std;
 
//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
 
//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }
 
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
 
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())
 
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
 
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18


int main() {
    int N;
    cin >>N;
    double sum;
    REP(i,N){
        double ai;
        cin >>ai;
        sum += 1/ai;
    }
    cout << setprecision(16) << 1/sum <<endl;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;

int main() {
	
  string s;
  cin >> s;
  
  if(s[0]=='M') {
    cout << 6 << endl;
    return 0;
  }
  if(s[0]=='T'&&s[1]=='U') {
    cout << 5 << endl;
    return 0;
  }
  if(s[0]=='W') {
    cout << 4 << endl;
    return 0;
  }
  if(s[0]=='T'&&s[1]=='H') {
    cout << 3 << endl;
    return 0;
  }
  if(s[0]=='F') {
    cout << 2 << endl;
    return 0;
  }
  if(s[0]=='S'&&s[1]=='A') {
    cout << 1 << endl;
    return 0;
  }
  if(s[0]=='S'&&s[1]=='U') {
    cout << 7 << endl;
    return 0;
  }
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define EPS (1e-10)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int bit[400000];

void add(int k,int x){
	while(k<400000){
		bit[k]+=x;
		k+=k&-k;
	}
}
int sum(int k){
	int res=0;
	while(k){
		res+=bit[k];
		k-=k&-k;
	}
	return res;
}
int a[200000];

signed main(){
	int n;scanf("%d",&n);
	vector<int>v;
	rep(i,n){
		scanf("%d",&a[i]);
		v.push_back(a[i]);
	}
	sort(v.begin(),v.end());
	rep(i,n){
		a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
		add(a[i],1);
	}
	rep(i,n){
		add(a[i],-1);
		int l=0,r=400000;
		int A=n/2;
		while(l!=r){
			int t=(l+r)/2;
			if(sum(t)>=A)r=t;
			else l=t+1;
		}
		printf("%d\n",v[l-1]);
		add(a[i],1);
	}
}

Measured memory_bytes: 4724
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<cmath>
#include <numeric>


#define REP(i,n) for (int i = 0; (i) < (n); ++ (i))
#define FOR(i,n) for (int i = 1; (i) <= (n); ++ (i))
#define lint long long

using namespace std;
int n,k;
int ans;
int x[200000];


int main(){
  cin >> n >> k;
  REP(i,n) cin >> x[i];
  ans = abs(x[0]-x[k-1])+min(abs(x[0]),abs(x[k-1]));
  int now = ans;
  for(int i = k;i<=n-1;i++){
    now = abs(x[i-(k-1)]-x[i])+min(abs(x[i-(k-1)]),abs(x[i]));
    if(now<ans) ans = now;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 640
import Control.Applicative

solver :: [Int] -> Bool
solver xs
     |no == 1 && n4 == 0 = False
     |n4 == no-1 && n2 ==0 = True
     |n4 >= no = True
     |otherwise = False
         where
	 no = length  [x|x<- xs, odd x]
	 n4 = length  [x|x<- xs, x `mod` 4 ==0]
	 n2 = length  [x|x<- xs, even x] - n4
 

myshow True = "Yes"
myshow False = "No"

main :: IO ()
main = do
    getLine
    xs <- map read . words <$> getLine 
    putStrLn $ myshow $ solver xs



Measured memory_bytes: 36220
#include<stdio.h>
#include<string.h>
#include <math.h>
#include <stdlib.h>
#define MAX 10000


typedef struct point{
  double x;
  double y;
} node;

void kock(int, node, node);

int main(){
  int n;
  node a,b;

  scanf("%d",&n);

  a.x = 0;
  a.y = 0;
  b.x = 100;
  b.y = 0;
  
  kock(n,a,b);
  printf("%.8f %.8f\n",b.x,b.y);

  return 0;
}

void kock(int n, node c, node d){
  node s,t,u;
  double r = M_PI / 3.0;

  if(n == 0){
    printf("%.8f %.8f\n",c.x,c.y);
    return;
  }

  s.x = (2.0 * c.x + 1.0 * d.x) / 3.0;
  s.y = (2.0 * c.y + 1.0 * d.y) / 3.0;
  u.x = (1.0 * c.x + 2.0 * d.x) / 3.0;
  u.y = (1.0 * c.y + 2.0 * d.y) / 3.0;
  t.x = (u.x - s.x) * cos(r) - (u.y - s.y) * sin(r) + s.x;
  t.y = (u.x - s.x) * sin(r) + (u.y - s.y) * cos(r) + s.y;

  kock(n - 1, c, s);
  kock(n - 1, s, t);
  kock(n - 1, t, u);
  kock(n - 1, u, d);
}



Measured memory_bytes: 2148
#include <bits/stdc++.h>
const int mod = 1000000007;
const int modx = 998244353;
#define ll long long
#define readi(x) scanf("%d", &x)
#define reads(x) scanf("%s", x)
#define readl(x) scanf("%I64d", &x)
#define rep(i, n) for (i = 0; i < n; i++)
#define rep1(i, a, b) for (i = a; i < b; i++)
#define rep2(i, a, b) for (i = b; i >= a; i--)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define bpc(x) __builtin_popcount(x)
#define pll pair<ll, ll>
#define pii pair<int, int>
#define pdd pair<double, double>
#define pic pair<int, char>
#define ddouble long double
#define PI 3.1415926535
#define endl "\n"
#define vi vector<int>
#define vll vector<long long>
#define vvi vector<vi>
#define all(x) x.begin(), x.end()
#define prod(x, y) ((x % mod) * (y % mod)) % mod
#define add(x, y) ((x % mod) + (y % mod)) % mod
#define ub(a, b) upper_bound(all(a), b)
#define lb(a, b) lower_bound(all(a), b)
#define pqs priority_queue<int, vector<int>, greater<int>>
#define pqb priority_queue<int>
#define mii map<int, int>
#define mll map<ll, ll>
using namespace std;
//using namespace __gnu_pbds;
/*ll power(ll x, ll y)
{
    ll r = 1;
    x = x % mod;
    while (y > 0)
    {
        if (y & 1)
            r = (r*x) % mod;

        y = y>>1;
        x = (x*x) % mod;
    }
    return r;
}*/
string s, t;
int n, m;
ll dp[3000][3000] = {}, vis[3000][3000] = {};
int rec(int x, int y)
{
    if (x >= n || y >= m)
        return 0;
    if (vis[x][y])
        return dp[x][y];
    vis[x][y] = 1;
    if (s[x] == t[y])
        return dp[x][y] = 1 + rec(x + 1, y + 1);
    ll ans = max(rec(x + 1, y), rec(x, y + 1));
    return dp[x][y] = ans;
}
void thunder()
{
    cin >> s >> t;
    n = s.size();
    m = t.size();
    //memset(dp, -1, sizeof(dp));
    rec(0, 0);
    string x;
    int i, j;
    i = 0;
    j = 0;
    while (i < n && j < m)
    {
        if (s[i] == t[j])
        {
            x = x + s[i];
            i++;
            j++;
        }
        else
        {
            if (dp[i + 1][j] > dp[i][j + 1])
                i++;
            else
                j++;
        }
    }
    cout << x << endl;
    return;
}
int main()
{
    /*#ifndef ONLINE_JUDGE
	    freopen("input.txt", "r", stdin);
	    freopen("output.txt", "w", stdout);
	#endif*/
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll q = 1;
    //cin >> t;
    while (q--)
        thunder();
}


Measured memory_bytes: 144528
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <cctype>
#include <numeric>
using namespace std;

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

struct State {int i, j;};

bool visited[52][52][52][52];
char lm[52][52], rm[52][52];
int W, H;
const int di[] = {0, -1, 0, 1};
const int ldj[] = {-1, 0, 1, 0};
const int rdj[] = {1, 0, -1, 0};

int main() {
  while (scanf("%d%d", &W, &H), W) {
    rep(i,H) scanf("%s%s", lm[i], rm[i]);
    int sli, slj, sri, srj;
    rep(i,H) {
      rep(j,W) {
        if (lm[i][j] == 'L') {sli = i, slj = j; lm[i][j] = '.';}
        if (rm[i][j] == 'R') {sri = i, srj = j; rm[i][j] = '.';}
      }
    }

    memset(visited, 0, sizeof visited);
    queue<State> LQ, RQ;
    LQ.push((State){sli, slj}); RQ.push((State){sri, srj});
    bool ok = false;
    while (!LQ.empty()) {
      State ls = LQ.front(), rs = RQ.front(); LQ.pop(); RQ.pop();
      if (visited[ls.i][ls.j][rs.i][rs.j]) continue;
      visited[ls.i][ls.j][rs.i][rs.j] = true;
      rep(i,4) {
        State nls = ls, nrs = rs;
        nls.i += di[i]; nls.j += ldj[i];
        nrs.i += di[i]; nrs.j += rdj[i];

        if (0 > nls.i || 0 > nls.j || nls.i >= H || nls.j >= W ||
            lm[nls.i][nls.j] == '#') nls = ls;
        if (0 > nrs.i || 0 > nrs.j || nrs.i >= H || nrs.j >= W ||
            rm[nrs.i][nrs.j] == '#') nrs = rs;

        if (lm[nls.i][nls.j] == '%' && rm[nrs.i][nrs.j] == '%') ok = true;
        if (lm[nls.i][nls.j] == '%' || rm[nrs.i][nrs.j] == '%') continue;
        if (visited[nls.i][nls.j][nrs.i][nrs.j]) continue;
        LQ.push(nls); RQ.push(nrs);
      }
    }
    printf("%s\n", ok ? "Yes" : "No");
  }
  return 0;
}

Measured memory_bytes: 10072
// {{{
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <complex>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define FOR(i, a, b) for(ll i = static_cast<ll>(a); i < static_cast<ll>(b); i++)
#define FORR(i, a, b) for(ll i = static_cast<ll>(a); i >= static_cast<ll>(b); i--)
#define REP(i, n) for(ll i = 0ll; i < static_cast<ll>(n); i++)
#define REPR(i, n) for(ll i = static_cast<ll>(n); i >= 0ll; i--)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> IP;
typedef pair<ll, LP> LLP;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

constexpr int INF = 100000000;
constexpr ll LINF = 10000000000000000ll;
constexpr int MOD = static_cast<int>(1e9 + 7);
constexpr double EPS = 1e-9;
// }}}

ll n, a[5];

void init()
{
}

void solve()
{
    ll m = a[0];
    FOR(i, 1, 5) m = min(m, a[i]);
    cout << n / m + (n % m == 0 ? 0 : 1) + 4 << endl;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    REP(i, 5) cin >> a[i];
    solve();
    return 0;
}

// vim:set foldmethod=marker:


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
struct ban
{
    int ans;
    char l, r;
    ban(){}
    ban(char x)
    {
        if (x == '0')
        {
            ans = 1;
        }
        else
        {
            ans = 0;
        }
        l = r = x;
    }
};
ban mer(const ban& l, const ban& r)
{
    ban res;
    res.l = l.l;
    res.r = r.r;
    res.ans = l.ans + r.ans;
    if (l.r == '0' && r.l == '0')
        res.ans--;
    return res;
}

int n, k;
char a[N];

ban t[N * 4];
void bil(int tl, int tr, int pos)
{
    if (tl == tr)
    {
        t[pos] = ban(a[tl - 1]);
        return;
    }
    int m = (tl + tr) / 2;
    bil(tl, m, pos * 2);
    bil(m + 1, tr, pos * 2 + 1);
    t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
}
ban qry(int tl, int tr, int l, int r, int pos)
{
    if (tl == l && tr == r)
        return t[pos];
    int m = (tl + tr) / 2;
    if (r <= m)
        return qry(tl, m, l, r, pos * 2);
    if (l > m)
        return qry(m + 1, tr, l, r, pos * 2 + 1);
    return mer(qry(tl, m, l, m, pos * 2), qry(m + 1, tr, m + 1, r, pos * 2 + 1));
}

bool stg(int d)
{
    for (int l = 1; l <= n - d + 1; ++l)
    {
        int r = l + d - 1;
        if (qry(1, n, l, r, 1).ans <= k)
            return true;
    }
    return false;
}

int byn()
{
    int l = 1, r = n;
    while ((r - l) > 3)
    {
        int m = (l + r) / 2;
        if (stg(m))
            l = m;
        else
            r = m;
    }
    for (int m = r; m >= l; --m)
        if (stg(m))
            return m;
}

int main()
{
    cin >> n >> k;
    cin >> a;
    bil(1, n, 1);
    cout << byn() << endl;
    return 0;
}


Measured memory_bytes: 2432
#include <bits/stdc++.h>
using namespace std;

template <typename T> class SegmentTree {
private:
  int n; function<T(T, T)> f; T t;
  vector<T> node;
public:
  SegmentTree() {};
  SegmentTree(function<T(T, T)> f, T t) : f(f), t(t) {}
  void init(int in) {
    n = 1;
    while (n < in) n <<= 1;
    node.assign(n << 1, t);
  }
  void build(const vector<T> &v) {
    int sz = v.size();
    init(sz);
    for (int i = 0; i < sz; i++) node.at(n + i) = v.at(i);
    for (int i = n - 1; i; i--) {
      node.at(i) = f(node.at((i << 1) | 0), node.at((i << 1) | 1));
    }
  }
  void update(int k, T a) {
    node.at(k += n) = a;
    while (k >>= 1) {
      node.at(k) = f(node.at((k << 1) | 0), node.at((k << 1) | 1));
    }
  }
  T query(int a, int b) {
    T vl = t, vr = t;
    for (int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) vl = f(vl, node.at(l++));
      if (r & 1) vr = f(node.at(--r), vr);
    }
    return f(vl, vr);
  }
};

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);
  auto f = [&](int x, int y) {return __gcd(x, y);};
  SegmentTree<int> ST(f, 0);
  ST.build(A);
  int ans = 0;
  for (int i = 0; i < N; i++) {
    int l = ST.query(0, i);
    int r = ST.query(i + 1, N);
    ans = max(ans, __gcd(l, r));
  }
  cout << ans << "\n";
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;

bool visited[10];
struct edge{
	int to;
	long long int cost;
};
vector<edge> tree[100010];
long long int cost_k[100010];

void dfs(int v,int par,long long int dist){
	cost_k[v]=dist;
	for(int i=0;i<(int)tree[v].size();++i){
		if(tree[v][i].to==par)continue;
		dfs(tree[v][i].to,v,dist+tree[v][i].cost);
	}
}

int main(){
	int n;cin>>n;

	for(int i=0;i<n-1;++i){
		int a,b,c;
		cin>>a>>b>>c;
		a--;b--;
		tree[a].push_back({b,c});
		tree[b].push_back({a,c});
	}
	int q,k;cin>>q>>k;
	k--;

	dfs(k,-1,0);

	for(int i=0;i<q;++i){
		int x,y;cin>>x>>y;
		x--;y--;
		cout<<cost_k[x]+cost_k[y]<<endl;
	}
}

Measured memory_bytes: 17408
#include <bits/stdc++.h>
using namespace std;
int main() {
    long long N; cin >> N;
    long long A[N];
    long long p[N], m[N];
    for(int i = 0; i < N; i++) {
        cin >> A[i];
        p[i] = A[i] + i;
        m[i] = i - A[i];
    }
    sort(p, p + N);
    sort(m, m + N);
    long long ans = 0;
    for (int i = 0; i < N; i++)
    {
        ans += abs(lower_bound(m, m + N, p[i]) - upper_bound(m, m + N, p[i]));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 8276
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define ll long long int
#define tc int t; cin>>t; while(t--)
#define inn ll arr[n]; for(int i=0;i<n;i++) cin>>arr[i];
#define fora(i,n); for(ll i=0;i<n;i++)
#define forb(i,a,n); for(int i=a;i<n;i++)
#define mod 1000000007
#define endl "\n"
#define F first
#define S second
#define vi vector<ll>
#define pii pair<ll,ll>
int main()
{
fastio
string s;
cin>>s;
for(auto &it:s)
    if(it=='?') it='D';

cout<<s<<"\n";


return 0; }

Measured memory_bytes: 3780
// {{{
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
// }}}

using ll = long long;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

struct state {
    int x, y, c;
    state () {}
    ~state() {}
    state(int x, int y, int c): x(x), y(y), c(c) {}
};

int H, W;
string F[50];

int main() {
    cin >> H >> W;
    for (int j = 0; j < H; ++j) cin >> F[j];

    int num_whites = 0;
    for (int j = 0; j < H; ++j) for (int k = 0; k < W; ++k) if (F[j][k] == '.') ++num_whites;

    queue<state> que;
    que.emplace(0, 0, 0);

    const int INF = 1 << 29;

    int min_dist[50][50];
    for (int j = 0; j < H; ++j) fill(min_dist[j], min_dist[j]+W, INF);
    min_dist[0][0] = 0;

    while (!que.empty()) {
        state st = que.front(); que.pop();
        for (int d = 0; d < 4; ++d) {
            int nx = st.x + dx[d], ny = st.y + dy[d];
            if (nx < 0 || H <= nx || ny < 0 || W <= ny) { continue; }
            if (F[nx][ny] == '#') continue;
            if (min_dist[nx][ny] == INF) {
                min_dist[nx][ny] = st.c + 1;
                que.emplace(nx, ny, st.c + 1);
            }
        }
    }

    cout << (min_dist[H-1][W-1] == INF ? -1 : (num_whites - min_dist[H-1][W-1] - 1)) << endl;


    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fr first
#define sc second
typedef long long ll;
const long long llinf=LLONG_MAX;
const int inf=INT_MAX;
const int nmax=1e5+5;
const int mod=1e9+7;
using namespace std;
int n,m,k,i,j;
int main() 
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>m>>k;
	if(k%n==0 || k%m==0)rc("Yes");
	for(i=1;i<=m;i++)for(j=1;j<=n;j++)if(i*n+j*m-2*i*j==k)rc("Yes");
	rc("No");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int retsu[15];
int ans = 0;
int n, m, q;
int a[55], b[55], c[55], d[55];
void dfs(int num, int last){
  //長さがnなら得点を数える
  // cout << "(" << num << "," << n << ")";
  if(num == n){
    int tmp = 0;
    for(int i=0;i<q;i++){
      if(retsu[b[i]-1]-retsu[a[i]-1]==c[i])tmp += d[i];
    }
    ans = max(ans, tmp);
    // cout << "[" << ans << "]";
    return;
  }
  for(int i=last;i<=m;i++){
    retsu[num]=i;
    dfs(num+1, i);
  }
}
int main(){
  cin >> n >> m >> q;
  
  for(int i=0;i<q;i++)cin >> a[i] >> b[i] >> c[i] >> d[i];
  
  dfs(0, 1);
  
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3676
#include <bits/stdc++.h>
using namespace std;
int main(){
	
	char arr[16];
	for(int i = 0 ; i<16 ; i++){
		cin >> arr[i];
	}
	
	int ans = 0;
	
	if(arr[0] != 'C'){
		ans++;
	}
	if(arr[1] != 'O'){
		ans++;
	}
	if(arr[2] != 'D'){
		ans++;
	}
	if(arr[3] != 'E'){
		ans++;
	}
	if(arr[4] != 'F'){
		ans++;
	}
	if(arr[5] != 'E'){
		ans++;
	}
	if(arr[6] != 'S'){
		ans++;
	}
	if(arr[7] != 'T'){
		ans++;
	}
	if(arr[8] != 'I'){
		ans++;
	}
	if(arr[9] != 'V'){
		ans++;
	}
	if(arr[10] != 'A'){
		ans++;
	}
	if(arr[11] != 'L'){
		ans++;
	}
	if(arr[12] != '2'){
		ans++;
	}
	if(arr[13] != '0'){
		ans++;
	}
	if(arr[14] != '1'){
		ans++;
	}
	if(arr[15] != '6'){
		ans++;
	}
	
	cout << ans; 

	return 0;
}


Measured memory_bytes: 256
N,K=map(int,input().split())
A=list(map(int,input().split()))
A_neg = []
A_pos = []
 
for i in range(N):
  if A[i] <= 0:
    A_neg.append(-A[i])
  else:
    A_pos.append(A[i])
 
A_neg.sort(reverse=True)
A_pos.sort(reverse=True)
 
ans = 1
 
if K == N:
  for i in range(N):
    ans *= (A[i]%1000000007)
    ans %= 1000000007
  print(ans)
 
elif K%2==1 and len(A_pos)==0:
  for i in range(1, K+1):
    ans *= ((-A_neg[-i])%1000000007)
    ans %= 1000000007
  print(ans)
 
else:
  if K%2==1:
    ans *= A_pos.pop(0)
    K -= 1
  buf = []
  for i in range(len(A_pos)//2):
    buf.append(A_pos[2*i]*A_pos[2*i+1])
  for i in range(len(A_neg)//2):
    buf.append(A_neg[2*i]*A_neg[2*i+1])
  buf.sort(reverse=True)
  for i in range(K//2):
    ans *= (buf[i]%1000000007)
    ans %= 1000000007
  print(ans)
  


Measured memory_bytes: 31884
#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout<<fixed<<setprecision(15); 
	int n; cin>>n;
	int p[n]; for (int i = 0; i < n; ++i) cin>>p[i];
	vector<int> dp(n+1,0); for (int i = 0; i < n; ++i) dp[p[i]]=dp[p[i]-1]+1;
	int ans=0;for (int i = 1; i <= n; ++i) ans=max(ans,dp[i]);
	cout<<n-ans<<endl;
	return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<map>
#include<bitset>

using namespace std;
using ll = long long;

#define rep(i, n) for(int i = 0;i < (n);i++)
#define repr(i, n) for(int i = (n);i >= 0;i--)
#define repf(i, m, n) for(int i = (m);i < (n);i++)

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1;} return 0;}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
//////////////////////////////////////////////////


int n, k;

int main() {
    cin >> n >> k;
    vector<int> h(n);
    rep(i, n) cin >> h[i];
    vector<int> dp(n+1, 1000000000);
    dp[0] = 0;
    repf(i, 1, n) {
        repf(j, 1, k+1) {
            if (i-j >= 0)
                chmin(dp[i], dp[i-j] + abs(h[i] - h[i-j]));
        }
    }
    cout << dp[n-1] << endl;
    return 0;
}


Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long
pair<int, int> A[200010];

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    rep(i, N) cin >> A[i].second >> A[i].first;
    sort(A, A + N);
    int sum = 0;
    rep(i, N) {
        sum += A[i].second;
        if (sum > A[i].first) {
            cout << "No" << endl;
            return 0;
        }
        //cout << sum << " " << A[i].first << endl;
    }
    cout << "Yes" << endl;


    return 0;
}


Measured memory_bytes: 3456
// #include <bits/stdc++.h>
#include <iostream>
#include <map>
#include <cmath>
#include <ios>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <stack>
#include <numeric>
// #include <windows.h>
using namespace std;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;
template<class T> using VVV = V<VV<T>>;
template<class T1, class T2> using P = pair<T1, T2>;
using I = int;
using D = double;
using B = bool;
using C = char;
using S = string;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = P<I, I>;
using VPII = V<PII>;
using PLL = P<LL, LL>;
using VPLL = V<PLL>;
using VI = V<I>;
using VVI = VV<I>;
using VLL = V<LL>;
using VVLL = VV<LL>;
using VC = V<C>;
using VVC = VV<C>;
using VS = V<S>;
using VVS = VV<S>;
using VB = V<B>;
using VVB = VV<B>;
#define REP(type, i, n) for (type i = 0; i < (type)(n); ++i)
#define REP2(type, i, m, n) for (type i = (m); i < (type)(n); ++i)
#define REPR(type, i, n) for (type i = (n)-1; i >= 0; --i)
#define REPR2(type, i, m, n) for (type i = (n)-1; i >= (m); --i)
#define REPx(x, a) for(auto x : a)
#define ALL(a) a.begin(), a.end()
#define SORT(a) sort(ALL(a))
#define SORTR(a, type) sort(ALL(a), G<type>())
#define REVERSE(a) reverse(ALL(a))
#define SIZE(a, type) ((type)(a).size())
#define bit_search(bit, n) REP(LL, bit, 1LL<<(n))
#define bit_check(bit, i) ((bit>>(i)) & 1)
#define setpre(n) fixed << setprecision((n))
#define UNIQUE(a) do {SORT(a); (a).erase(unique(ALL(a)), (a).end());} while(0)
#define MAX(a) *max_element(ALL(a))
#define MIN(a) *min_element(ALL(a))
#define bisect_left(a, x) lower_bound(ALL(a), (x)) - a.begin()
#define bisect_right(a, x) upper_bound(ALL(a), (x)) - a.begin()
#define INPUT(a) REPx(&x, a) cin >> x;
#define INPUTP(a) REPx(&x, a) cin >> x.first >> x.second;
#define OUTPUT_PERMUTATION(n) do{VI v(n); iota(ALL(v), 1); do{REPx(x, v) cout << x << " "; ENDL} while(next_permutation(ALL(v)));} while(0);
#define MAKE_PERMUTATION(n, PER) do{VVI a(fact(n), VI(n)); int idx = 0; VI v(n); iota(ALL(v), 1); do{REP(roop, n) a[idx][roop] = v[roop]; idx++;} while(next_permutation(ALL(v))); PER = a;} while(0); // int fact(), VVI PERを宣言しておく、n=10が限界(500 ms)
#define ENDL cout << endl;

const int INF = 2e9;
const LL MOD = 1e9 + 7;

template<class T> using PRIORITY_QUEUE = priority_queue< T, V<T>, greater<T> >;
template<class T> inline bool chmin(T &a, T b){if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){if (a < b) {a = b; return true;} return false;}
template<class T> inline void debug1(V<T> A){REP(int, i, SIZE(A, int)){if (A[i] == INF) cout << "I ";else cout << A[i] << " ";}ENDL}
template<class T> inline void debug2(VV<T> A){REP(int, i, SIZE(A, int)){REP(int, j, SIZE(A[i], int)){if (A[i][j] == INF) cout << "I "; else cout << A[i][j] << " ";}ENDL}}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, k;
  cin >> n >> k;
  VI p(n);
  INPUT(p);
  SORT(p);
  int ans = 0;
  REP(int, i, k) ans += p[i];
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3644
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#include<set>
#include<complex>
#include<map>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
#define MAX 9999999
using namespace std;
typedef pair<int, int> pii;
typedef pair<double,double>pdd;
typedef pair<ll,ll>pll;
int main(){
    string a,b; int c,d;string temp;
    while(true){
        cin>>a>>b;
        c=stoi(a); d=stoi(b);
        if(d+c==0)return 0;
        int hit=0,brow=0; vc v;
        rep(i,a.size())v.push_back(a[i]);
        rep(i,a.size()){if(a[i]==b[i])hit++;}
        rep(i,a.size())rep(j,a.size())if(b[i]==v[j])brow++;
        cout<<hit<<" "<<brow-hit<<endl;
    }
}

Measured memory_bytes: 2984
#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define ddrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define ssrep(i, s, t) for (int i = s; i <= t; ++i)

#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))

using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using ld = long double;

long int M = 1e+9+7;
int main(void){
    int n,m;
    cin >> n >> m;
    vector<bool> ma(n,false);
    /*
    rrep(i,m){
        cout << i << " " << n+t-i << endl;;
    }
    */
    int l=1,r=n;
    rep(i,m){
        int ma1=r-l-1,ma2=n-r+l-1;
        if(!ma[ma1] && !ma[ma2] && ma1 != ma2){
            cout << l << " " << r << endl;
            l++; r--;
            ma[ma1]=true; ma[ma2]=true;
        }else{
            r--; i--;
        }
    }
    return 0;
}

Measured memory_bytes: 3644
#include<iostream>
#include<string>
using namespace std;
int main()
{
  int i,t=0;
  string s;
  cin >> s;
  if(s[0]!='A'||s[1]<'a'||s[1]>'z'){
    cout << "WA" << endl;
    return 0;
  }
  for(i=2;i<s.size()-1;i++)
    if(s[i]<'a'||s[i]>'z'){
      if(t>0||s[i]!='C'){
        cout << "WA" << endl;
        return 0;
      }
      t++;
    }
  if(t==0||s[s.size()-1]<'a'||s[s.size()-1]>'z'){
    cout << "WA" << endl;
    return 0;
  }
  cout << "AC" << endl;
  return 0;
}

Measured memory_bytes: 256
N = int(input())
H = list(map(int,input().split()))
ans = "Yes"
RMH = [0]*N
# 右端から右からi番目の要素のうち最小の値
for i in range(N):
  if i == 0:
    RMH[i] = H[-i-1]
  else:
    RMH[i] = min([RMH[i-1],H[-i-1]]) #reversed

# 左からi番目の要素が、左からi+1番目から右端の要素の最小値との差が常に１以下ならOK
for i in range(N-1):
  if H[i] - RMH[-i-2] > 1:
    ans = "No"

print(ans)

Measured memory_bytes: 14396
a, b, c, d = list(input())
pm = ['+', '-']
s = []
for i in pm:
    for j in pm:
        for k in pm:
            s.append(a + i + b + j + c + k + d)

for i in s:
  if eval(i) == 7:
    print(i + '=7')
    exit()

Measured memory_bytes: 3060
import heapq
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
if sum(a) < sum(b) :
  print(-1)
else :
  ans = 0
  lack = 0
  que = [0]
  heapq.heapify(que)
  for i in range(n) :
    a[i] -= b[i]
    if a[i] < 0 :
      ans += 1
      lack -= a[i]
    else :
      heapq.heappush(que,-a[i])
  while lack > 0 :
    m = heapq.heappop(que)
    lack += m
    ans += 1
  print(ans)

Measured memory_bytes: 18484
#include <bits/stdc++.h>
using namespace std;

#define d(x) cerr << #x ":" << x << endl;
#define dd(x, y) cerr << "(" #x "," #y "):(" << x << "," << y << ")" << endl
#define rep(i, n) for (int i = (int)(0); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define dump(v)                  \
    cerr << #v ":[ ";            \
    for (auto macro_vi : v) {    \
        cerr << macro_vi << " "; \
    }                            \
    cerr << "]" << endl;
#define ddump(v)                           \
    cerr << #v ":" << endl;                \
    for (auto macro_row : v) {             \
        cerr << "[";                       \
        for (auto macro__vi : macro_row) { \
            cerr << macro__vi << " ";      \
        }                                  \
        cerr << "]" << endl;               \
    }
using lint       = long long;
const int INF    = 1e9;
const lint LINF  = 1e18;
const double EPS = 1e-10;

int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> G(H);
    rep(i, H) cin >> G[i];

    int ma = -1;
    rep(sx, H) rep(sy, W) {
        vector<vector<int>> dist(H, vector<int>(W, INF));
        dist[sx][sy] = 0;
        queue<pair<int, int>> q({{sx, sy}});
        while (!q.empty()) {
            int cx, cy;
            tie(cx, cy) = q.front();
            q.pop();
            for (int k = 0; k < 4; k++) {
                int nx = cx + dx[k], ny = cy + dy[k];
                if (0 <= nx && nx < H && 0 <= ny && ny < W &&
                    dist[nx][ny] == INF && G[nx][ny] != '#') {
                    dist[nx][ny] = dist[cx][cy] + 1;
                    q.push({nx, ny});
                }
            }
        }
        // dd(sx, sy);
        // ddump(dist);

        rep(i, H) rep(j, W) {
            if (G[sx][sy] == '.' && G[i][j] == '.') ma = max(ma, dist[i][j]);
        }
    }
    cout << ma << endl;
    return 0;
}

Measured memory_bytes: 3580
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------
int N, M;
int A[201010], B[201010];
int d[201010];
bool used[201010];

struct edge {
  int to, cost;
};
typedef pair<int, int> P;

vector<edge> G[201010];

void dijkstra(int s) {
  priority_queue<P, vector<P>, greater<P> > que;

  fill(d, d + N + 1, inf);
  d[s] = 0;
  que.push(P(0, s));

  while (!que.empty()) {
    P p = que.top();
    que.pop();
    int v = p.second;
    if (d[v] < p.first) continue;
    for (int i = 0; i < G[v].size(); ++i) {
      edge e = G[v][i];
      if (d[e.to] > d[v] + e.cost) {
        d[e.to] = d[v] + e.cost;
        que.push(P(d[e.to], e.to));
      }
    }
  }
}

int main() {
  cin >> N >> M;
  repe(i, 1, M) {
    cin >> A[i] >> B[i];
    G[A[i]].push_back(edge{B[i], 1});
    G[B[i]].push_back(edge{A[i], 1});
  }

  dijkstra(1);

  cout << "Yes" << endl;

  repe(i, 2, N) {
    int mind = inf;
    int minto = inf;
    for (auto e : G[i]) {
      int to = e.to;
      if (mind > d[to]) {
        mind = d[to];
        minto = to;
      }
    }
    cout << minto << endl;
  }
}


Measured memory_bytes: 16888
#include<iostream>
#include<string>
using namespace std;

int main()
{
	int n;
	string Taro, Hanako;
	int Tscore=0, Hscore=0;
	int i;
	
	cin >> n;
	
	for(i=0;i<n;i++){
		cin >> Taro >> Hanako;
		
		if(Taro==Hanako){
			Tscore++;
			Hscore++;
		}
		else if(Taro>Hanako)
			Tscore+=3;
		else if(Hanako>Taro)
			Hscore+=3;
	}
	
	cout << Tscore << ' ' << Hscore << endl;
	
	return 0;
}

Measured memory_bytes: 1204
#include <bits/stdc++.h>
using namespace std;

#define ll int

int main()
{
    ll n;
    cin >> n;

    ll next = 1;
    ll breakCount = 0;
    for (int i = 0; i < n; ++i)
    {
        int input;
        cin >> input;
        if (input == next)
        {
            next++;
        }
        else
        {
            breakCount++;
        }
    }

    if (breakCount == n)
    {
        breakCount = -1;
    }

    cout << breakCount << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long N,cost[100001][3],DP[100001][3];
int main()
{
	cin>>N;
	for(int i=1;i<=N;i++)
	{
		for(int j=0;j<3;j++)
		{
			cin>>cost[i][j];
		}
	}
	DP[0][0]=0;
	DP[0][1]=0;
	DP[0][2]=0;
	cost[0][0]=0;
	cost[0][1]=0;
	cost[0][2]=0;
	for(int k=1;k<=N;k++)
	{
		for(int j=0;j<3;j++)
		{
			DP[k][j]=0;
			if(j==0)
			{
				DP[k][j]=max(DP[k-1][1],DP[k-1][2])+cost[k][j];
			}
			else if(j==1)
			{
				DP[k][j]=max(DP[k-1][0],DP[k-1][2])+cost[k][j];
			}
			else
			{
				DP[k][j]=max(DP[k-1][1],DP[k-1][0])+cost[k][j];
			}
		}
	}
	long long res=0;
	for(int i=0;i<3;i++)
	{
		res=max(res,DP[N][i]);
	}
	cout<<res<<endl;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	ll n, x;
	cin >> n >> x;

	ll numP[51], num[51];
	numP[0] = 1;
	num[0] = 1;
	for (int i = 1;i <= 50;i++) {
		numP[i] = 2 * numP[i - 1] + 1;
		num[i] = 2 * num[i - 1] + 3;
	}

	ll ans = 0;
	while (n > 1) {
		if (x == 1) {
			cout << ans << endl;
			return 0;
		}
		if (x <= 1 + num[n - 1]) {
			n--;
			x--;
			continue;
		}
		ans += numP[n - 1];
		ans++;
		if (x == 2 + num[n - 1]) {
			cout << ans << endl;
			return 0;
		}
		if (x <= 2 * num[n - 1] + 2) {
			x -= 2 + num[n - 1];
			n--;
			continue;
		}
		ans += numP[n - 1];
		cout << ans << endl;
		return 0;
	}
	if (x >= 2 && x <= 4) {
		ans += x - 1;
	}
	if (x == 5) {
		ans += 3;
	}

	cout << ans << endl;



	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>


using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
#define reps(i,n) for (int i = 1; i <= (int)(n); ++i)
#define repd(i,n) for (int i = (int)(n - 1); i >= 0; --i)
#define repds(i,n) for (int i = (int)(n); i > 0; --i)
#define loop(i,x,n) for (int i = (int)(x); i < (n); ++i)
#define loops(i,x,n) for (int i = (int)(x); i <= (n); ++i)
#define loopd(i,x,n) for (int i = (int)(x); i > (n); --i)
#define loopds(i,x,n) for (int i = (int)(x); i >= (n); --i)
#define itrep(i,s) for (auto i = begin(s); i != end(s); ++i)
#define itrepd(i,s) for (auto i = --end(s); i != begin(s); --i)
#define all(f,x,...) [&](decltype(x)& whole) { return (f)(begin(whole), end(whole), ##__VA_ARGS__); }(x)
#define rall(f,x,...) [&](decltype(x)& whole) { return (f)(rbegin(whole), rend(whole), ##__VA_ARGS__); }(x)
using ll = long long;
using ld = long double;
constexpr ll inf = static_cast<ll>(1e17);
constexpr int iinf = static_cast<int>(1e9);
constexpr double dinf = 1e10;
constexpr ld ldinf = 1e17;
constexpr ll mod = static_cast<ll>(1e9 + 7);
std::ostream& endn(std::ostream& os) { return os.put(os.widen('\n')); }
template<class T> constexpr int sz(const T& a) { return (int)a.size(); }
template<class T, class ... Args> constexpr T mins(T& a, Args... args) { return a = min<T>({ a, args... }); }
template<class T, class... Args> constexpr T maxs(T& a, Args... args) { return a = max<T>({ a,args... }); }

int n;
ll a[100005], b[100005];
map<ll, int> place;
void solve() {
    cin >> n;

    rep(i, n) cin >> a[i];

    copy(a, a + n, b);
    sort(b, b + n);

    rep(i, n) place[b[i]] = i;

    int ans = 0;
    rep(i, n) if (i % 2 != place[a[i]] % 2) ++ans;

    cout << ans / 2 << endn;

}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    cout << flush;
    return 0;
}


Measured memory_bytes: 8064