akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  size_t N;
  cin >> N;
  multiset<int, greater<int>> s(greater<int>{});
  auto num = pow(2, N);
  for (size_t i = 0; i < num; ++i) {
    int S;
    cin >> S;
    s.emplace(S);
  }
  vector<int> done;
  done.reserve(num / 2);

  vector<int> adding;
  adding.reserve(num / 2);

  auto it = s.begin();
  adding.emplace_back(*it);
  s.erase(it);

  while (!s.empty()) {
    for (int val : adding) {
      done.emplace_back(val);
    }
    adding.clear();
    sort(done.rbegin(), done.rend());
    for (int val : done) {
      auto it = s.upper_bound(val);
      if (it == s.end()) {
        cout << "No" << endl;
        return 0;
      }
      adding.emplace_back(*it);
      s.erase(it);
    }
  }
  cout << "Yes" << endl;
}


Measured memory_bytes: 13568
N, L = map(int, input().split())
A = []
for i in range(N):
    A.append(L+i)
B = []
for j in range(N):
    B.append(sum(A)-A[j])

if N > abs(L) and L < 0:
    print(sum(A))
elif max(B) < 0:
    print(min(B))
else:
    print(max(B))


Measured memory_bytes: 3060
a, b, c, d = map(int, input().split())
def gcd(a,b):
   while b != 0:
      a, b = b, a%b
   return a
def lcm(a,b):
   return int(a*b / gcd(a,b))
cnt = 0
quo_c = b//c - (a-1)//c
quo_d = b//d - (a-1)//d
quo_cd = b//lcm(c,d) - (a-1)//lcm(c,d)
print(b - (a-1) - quo_c - quo_d + quo_cd)

Measured memory_bytes: 3064
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<map>
#include<queue>
#include<vector>
using namespace std;

int main() {
	int a[4], b[4];
	while (cin >> a[0] >> a[1] >> a[2] >> a[3] >> b[0] >> b[1] >> b[2] >> b[3]) {
		int H = 0, B = 0;
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++)
				if (a[i] == b[j])B++;
			if (a[i] == b[i]) {
				B--; H++;
			}
		}
		cout << H << " " << B << endl;
	}

	return 0;
}

Measured memory_bytes: 1160
#template
def inputlist(): return [int(j) for j in input().split()]
#template
N = int(input())
if N == 1:
    print(0)
    exit()

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

li = factorization(N)
n = len(li)
ans = 0
counts = [1]*40
for i in range(2,41):
    counts[i-1] = counts[i-2]+i
from bisect import bisect_right
for i in range(n):
    count = li[i][1]
    ans += bisect_right(counts,count)
print(ans)


Measured memory_bytes: 9412
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Linq;
using System.Numerics;

namespace AtCoderWorkspace
{
    public class Solver
    {
        public void Solve()
        {
            var cin = new Scanner();
            var n = cin.nextInt();            
            Console.WriteLine(n==0?1:0);
        }
    }

    class Scanner
    {
        string[] s;
        int i;

        char[] cs = new char[] { ' ' };

        public Scanner()
        {
            s = new string[0];
            i = 0;
        }

        public string next()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return next();
            i = 0;
            return s[i++];
        }

        public int nextInt()
        {
            return int.Parse(next());
        }
        public int[] ArrayInt(int N, int add = 0)
        {
            int[] Array = new int[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt() + add;
            }
            return Array;
        }

        public int[] DPArrayInt(int N, int ex)
        {
            int[] Array = new int[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt();
            }
            return Array;
        }

        public long nextLong()
        {
            return long.Parse(next());
        }

        public long[] ArrayLong(int N, long add = 0)
        {
            long[] Array = new long[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong() + add;
            }
            return Array;
        }

        public long[] DPArrayLong(int N, int ex)
        {
            long[] Array = new long[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong();
            }
            return Array;
        }

        public double nextDouble()
        {
            return double.Parse(next());
        }


        public double[] ArrayDouble(int N, double add = 0)
        {
            double[] Array = new double[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextDouble() + add;
            }
            return Array;
        }
    }

    class Program
    {
        static void Main(string[] s) => new Solver().Solve();
    }
}


Measured memory_bytes: 27528
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <numeric>
#define ll long long int
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
using namespace std;
int mx4[] = {0,1,0,-1};
int my4[] = {1,0,-1,0};
int mx2[] = {1,0};
int my2[] = {0,1};
#define pb push_back 

int main(){
    int n; cin >> n;
    vector<int> h(n);
    rep(i,n) cin >> h[i];

    vector<int> dp(n);
    dp[1] = abs(h[1] - h[0]);
    for(int i=1;i<n-1;i++){
        dp[i+1] = min(dp[i] + abs(h[i+1]-h[i]),dp[i-1] + abs(h[i+1]-h[i-1]));
    }
    cout << dp[n-1] << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
long long inv[200010];
vector<int> e[200010];
vector<int> v[200010];

void pre() {
    inv[0] = 1; inv[1] = 500000004;
    for (int i = 2; i < 200010; i++) inv[i] = inv[i-1] * inv[1] % mod;
}

int search(int curr, int prev, int n) {
    int all = 0;
    int q = 0;
    for (auto &to: e[curr]) {
        if (to == prev) continue;
        auto s = search(to, curr, n);
        v[curr].emplace_back(s);
        all += s;
    }
    if (n-1 != all) v[curr].emplace_back(n-all-1);
    return all + 1;
}

long long calc(int i, int n) {
    long long ret = inv[1] - inv[n] + mod; ret %= mod;
    for (auto &x: v[i]) {
        ret -= inv[n-x] - inv[n];
        ret = (ret + mod) % mod;
    }
    if (v[i].size() <= 1) ret = 0;
    return ret;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    pre();
    int n; cin >> n;
    for (int i = 0; i < n-1; i++) {
        int a, b; cin >> a >> b; a--; b--;
        e[a].emplace_back(b); e[b].emplace_back(a);
    }
    search(0, -1, n);
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans += calc(i, n); ans %= mod;
    }
    cout << ans << "\n";
    return 0;
}

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

using namespace std;
using ll = long long;


int main()
{
    int n,m;
    cin >> n >> m;
    vector<vector<ll>> hen(n,vector<ll>(n,1e12));

    for(int i = 0; i < m; i++){
        int a,b,c;
        cin >> a >> b >> c;
        hen[a][b] = c;
    }

    for(int i = 0; i < n; i++)hen[i][i] = 0;

    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                hen[i][j] = min(hen[i][j], hen[i][k] + hen[k][j]);
            }
        }
    }

    for(int i = 0; i < n; i++)if(hen[i][i] < 0){cout << "NEGATIVE CYCLE" << endl;return 0;}

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++)cout << (hen[i][j] >= 1e11 ? "INF" : to_string(hen[i][j])) << (j == n - 1 ? '\n' : ' '); 
    }
}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
//#define Fast ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
typedef vector<int>Vl;
typedef pair<int,int>PII;
typedef vector<PII>Vll;
typedef vector<pair<int,pair<int,int> > >Vlll;
typedef priority_queue<int>PQL;
typedef map<int,int>MP;
#define S second
#define F first
#define mp make_pair
#define ms(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define sl(n) scanf("%lld",&n)
#define pl(n) printf("%lld",n)
const int mod=1e18+5;
signed main(){
  int dp[505][505];
  int n;
  sl(n);
  int arr[n];
  int prefix[n+1];
  ms(prefix,0);
  for(int i=0;i<n;i++)sl(arr[i]);
  
  auto sum=[&](int L,int R){
	  int s=0;
	  for(int i=L;i<=R;i++){
		  s+=arr[i];
	  }
	  return s;
  };

  
  for(int L=n-1;L>=0;L--)
  {
	  for(int R=L;R<n;R++)
	  {
		  if(L==R)dp[L][R]=0;
		  else{
			  dp[L][R]=mod;
			  int sumso=sum(L,R);
			  for(int i=L;i<=R-1;i++){
				  dp[L][R]=min(dp[L][R],dp[L][i]+dp[i+1][R]+sumso);
				  
			  }
		    }  
	  }
  }
  cout<<dp[0][n-1]<<endl;
   
  return 0;
}


Measured memory_bytes: 1792
#!/usr/bin/env python
#-*- coding:utf-8 -*-
import heapq

while True:
	# 割引券，駅，路線，スタート，ゴール
	c, n, m, s, d = map(int, raw_input().split())
	if not (c or n or m or s or d): break
	field = {}
	for i in xrange(m):
		a, b, f = map(int, raw_input().split())
		field[(a, b)] = field[(b, a)] = f;
	visited = {}
	q = []
	heapq.heappush(q, (0, c, s))
	while q:
		cost, rem, pos = heapq.heappop(q)
		if pos == d:
			print cost
			break
		for i in xrange(1, n + 1):
			edge = (pos, i)
			next = (rem, i)
			ncost = cost + field.get(edge, 0x7fffffff)
			if ncost < visited.get(next, 0x7fffffff):
				heapq.heappush(q, (ncost, rem, i))
				visited[next] = ncost
			next = (rem - 1, i)
			ncost = cost + field.get(edge, 0x7fffffff) / 2
			if rem > 0 and ncost < visited.get(next, 0x7fffffff):
				heapq.heappush(q, (ncost, rem - 1, i))
				visited[next] = ncost

Measured memory_bytes: 5012
#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return (a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return (a>b)?a=b,1:0;}
inline int read() {
	rint s=0;
	rgt char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
	return s;
}
int main()
{
	rint a,b;
	a=read(),b=read();
	if(a<10&&b<10) printf("%d",a*b);
	else printf("-1");
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int prime[1000000]; // 1 -> prime, 0 -> not prime                               

void setPrime() {                                                               
    int i, j;                                                                   
                                                                                
    for (i = 2; i < 1000000; i++) {                                             
        prime[i] = 1;                                                           
    }                                                                           
                                                                                
    for (i = 2; i < 1000000; i++) {                                             
        if (prime[i] == 1) {                                                    
            for (j = i * 2; j < 1000000; j += i) {                              
                prime[j] = 0;                                                   
            }                                                                   
        }                                                                       
    }                                                                           
}

int main(void) {                                                                
    int i, n;                                                                   
    int count = 0;                                                              
                                                                                
    setPrime();                                                                 
    while (scanf("%d", &n) != EOF) {                                            
        count = 0;                                                              
        for (i = 2; i <= n; i++) {                                              
            count += prime[i];                                                  
        }                                                                       
        printf("%d\n", count);                                                  
    }                                                                           
                                                                                
    return 0;                                                                   
}

Measured memory_bytes: 4500
coins_500 = int(input())
coins_100 = int(input())
coins_50 = int(input())
X = int(input())

cnt = 0
for coin_500 in range(0, coins_500+1):
  for coin_100 in range(0, coins_100+1):
    for coin_50 in range(0, coins_50+1):
      if coin_500 * 500 + coin_100 * 100 + coin_50 * 50 == X:
        cnt +=1

print(cnt)

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

int n;

int main() {
	ios::sync_with_stdio(0);
	cin >> n;
	n %= 10;
	switch(n) {
		case 2:
		case 4:
		case 5:
		case 7:
		case 9:
			cout << "hon";
			break;
		case 0:
		case 1:
		case 6:
		case 8:
			cout << "pon";
			break;
		case 3:
			cout << "bon";
	}
//	system("pause");
	return 0;
}

Measured memory_bytes: 3608
import java.util.*;
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayDeque<Character> stack = new ArrayDeque<>();
        char arr[] = sc.next().toCharArray();
        for(int i = 0 ; i < arr.length ; i++){
            if(arr[i] == 'S'){
                stack.push('S');
            } else {
                if(!stack.isEmpty() && stack.peek() == 'S'){
                    stack.pop();
                } else {
                    stack.push('T');
                }
            }
        }
        System.out.println(stack.size());
    }
}

Measured memory_bytes: 28516
#include <iostream>
#include <algorithm>
#include <cstring>
#include <functional>
#include <bits/stdc++.h>


using namespace std;


int main()
{
    //std::ios_base::sync_with_stdio(false); 10.566
    string s,t;
    cin>>s>>t;
    cout<<t+s<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std;

bool saiki( char stage[101][101], int xs, int ys, int xg, int yg, int w, int h, bool data[101][101] )
{
	data[xs][ys] = true;
	if( xs == xg && ys == yg ) return true;
	if( xs + 1 <= w && stage[xs + 1][ys] == stage[xs][ys] && data[xs + 1][ys] == false )if( saiki( stage, xs + 1, ys, xg, yg, w, h, data ) ) return true;
	if( xs - 1 >= 1 && stage[xs - 1][ys] == stage[xs][ys] && data[xs - 1][ys] == false ) if( saiki( stage, xs - 1, ys, xg, yg, w, h, data ) ) return true;
	if( ys + 1 <= h && stage[xs][ys + 1] == stage[xs][ys] && data[xs][ys + 1] == false ) if( saiki( stage, xs, ys + 1, xg, yg, w, h, data ) ) return true;
	if( ys - 1 >= 1 && stage[xs][ys - 1] == stage[xs][ys] && data[xs][ys - 1] == false ) if( saiki( stage, xs, ys - 1, xg, yg, w, h, data  ) ) return true;

	return false;
}


int main(int argc, char const* argv[])
{
	char stage[101][101];
	bool data[101][101];
	int w,h;
	int xs,ys;
	int xg,yg;
	int n;

	while( cin >> w >> h && w != 0 ){
		cin >> xs >> ys;
		cin >> xg >> yg;
		cin >> n;

		for( int i = 0;i < 101;i++ ){
			for( int j = 0;j < 101;j++ ){
				stage[i][j] = 0;
				data[i][j] = false;
			}
		}

		for( int i = 0;i < n;i++ ){
			int c,d,x,y;
			cin >> c >> d >> x >> y;

			if( d == 0 ){
				for( int j = 0;j < 2;j++ ){
					for( int k = 0;k < 4;k++ ){
						stage[k + x][j + y] = c;
					}
				}
			} else if( d == 1 ){
				for( int j = 0;j < 4;j++ ){
					for( int k = 0;k < 2;k++ ){
						stage[k + x][j + y] = c;
					}
				}
			}
		}
		if( saiki( stage, xs, ys, xg, yg, w, h ,data ) ) cout << "OK" << endl;
		else cout << "NG" << endl;
	}

	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define bit(x) (1L << (x))
using ll = long long;
using namespace std;

template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
 
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}

struct State{
  ll t, m, x;

  bool operator<(const auto& ot){
    return t != ot.t ? t < ot.t : m > ot.m;
  }
};

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

  vector<State> st;
  REP(i, n){
    ll s, t, x; cin >> s >> t >> x;
    st.push_back({s-x, 0, x});
    st.push_back({t-x, 1, x});
  }

  sort(st.begin(), st.end());

  set<int> xx;
  for(int i=0, j=0; i<q; i++){
    int d; cin >> d;

    while(j < 2*n && st[j].t <= d){
      // operate event
      if(st[j].m == 0)
        xx.insert(st[j].x);
      else 
        xx.erase(st[j].x);

      j++;
    }

    if(xx.size() == 0)
      cout << -1 << endl;
    else 
      cout << *xx.begin() << endl;

  }
  return 0;
}


Measured memory_bytes: 20968
#include<bits/stdc++.h>
using namespace std;
int num=-1,c=1,a;
int main(){
  cin>>a;
  vector<int> b(a);
  for(int i=0;i<a;i++)cin>>b[i];
  for(int i=0;i<a;i++){
    if(c==2){
      num=i;
      break;
    }
    c=b[c-1];
  }
  cout<<num<<endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include<cstdlib>
using namespace std;
typedef struct listpoint
{
    string data;
    listpoint *next=NULL;
} listpoint;
int main ()
{
    string s1,s2;
    unsigned int l=0;
    getline(cin,s1);
    getline(cin,s2);
    if(s1.length()<=100&&s1.length()>=2)
    {
        if(s1.length()==s2.length())
        {
            for(unsigned int i=0; i<s1.length(); ++i)
            {
                l=0;
                for(unsigned int j=0;; j=(j+1)%s2.length())
                {
                    if(s1[(i+j)%s2.length()]!=s2[j])
                    {
                        break;
                    }else
                    {
                        l++;
                    }
                    if(l==s1.length())
                    {
                        cout<<"Yes"<<endl;
                        return 0;
                    }
                }
            }
        }
    }
    cout<<"No"<<endl;
    return 0;
}


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

void solve(long long N, std::vector<long long> s)
{
    // A - B = CとおいてCについて考える
    // 経由する番号は順に
    // 0, A, C, A+C, 2C, A+2C, …, kC, A+kC(=N-1)
    ll ans = 0;
    for (ll c = 1; c <= N; c++) {
        ll score = 0;

        for (ll k = 0; k * c < N - 1; k++) {
            auto l = k * c; // 0, C, 2C, …, kCの列
            auto r = N - 1 - k * c; // A, A+C, A+2C, …, A+kCの列
            if (((N - 1) % c == 0) && l >= r) {
                // N-1 が C(=A-B) で割り切れる場合、かならず中央でぶつかる
                break;
            }
            if (r <= c) {
                // そうでない場合、rは最初のAまでは行ける(？)
                break;
            }
            score += s[l] + s[r];
            ans = max(ans, score);
        }
    }
    cout << ans << endl;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
// clang-format off
#pragma GCC diagnostic ignored "-Wunused-result"
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long N;
    scanf("%lld",&N);
    std::vector<long long> s(N-1-0+1);
    for(int i = 0 ; i < N-1-0+1 ; i++){
        scanf("%lld",&s[i]);
    }
    solve(N, std::move(s));
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
long long n,m,p;
struct node
{
	int w,v;
	bool friend operator<(const node &a,const node &b)
	{
		return a.w<b.w;
	}
};
node save[3005];
long long dp[3005][6005];
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>save[i].w>>save[i].v;
	sort(save+1,save+1+n);
	for(int i=1;i<=n;i++)
		for(int k=0;k<save[i].w+m;k++)
		{
			if(k>=save[i].w) dp[i][k]=max(dp[i-1][k],dp[i-1][k-save[i].w]+save[i].v);
			else dp[i][k]=dp[i-1][k];
		}
	long long res=0;
	for(int i=1;i<=n;i++) res=max(dp[n][m+save[i].w-1],res);
	cout<<res<<endl;
	return 0;
}

Measured memory_bytes: 141056
#import numpy as np
N = int(input())
a = [0]+list(map(int,input().split()))
ans = [0]*(N+1)
an = []
for i in range(N,0,-1):
  c =0
  c = sum(ans[2*i::i])
  if c%2!=a[i]:
    ans[i]=1
    an.append(i)
print(len(an))
for i in range(len(an)):
  print(an[i],end=" ")


Measured memory_bytes: 13148
n = int(input())
S = list(map(int,input().split()))
q = int(input())
T = list(map(int,input().split()))
def bisearch(t):
    L = -1
    U = n
    while U-L >1:
        x = (L+U)//2
        if S[x] > t:
            U = x
        elif S[x] < t:
            L =x
        else:
            return True
    return False
ans = 0
for t in T:
    if bisearch(t):
        ans += 1

print(ans)
    
    


Measured memory_bytes: 16708
<?php

fscanf(STDIN, "%d", $n);
$a_arr = [];
$x_arr = [];
$y_arr = [];
for ($i = 0; $i < $n; ++$i) {
    fscanf(STDIN, "%d", $a);
    $a_arr[] = $a;

    for ($j = 0; $j < $a; ++$j) {
        fscanf(STDIN, "%d %d", $x, $y);
        $x_arr[$i][] = $x;
        $y_arr[$i][] = $y;
    }
}

$max = 0;
for ($bit = 0; $bit < (1 << $n); ++$bit) {
    $honests = [];
    for ($i = 0; $i < $n; ++$i) {
        if ($bit & (1 << $i)) {
            $honests[] = $i;
        }
    }

    $flg = true;
    foreach ($honests as $honest) {
        for ($j = 0; $j < $a_arr[$honest]; ++$j) {
            if (
                ($y_arr[$honest][$j] == 1 && !in_array($x_arr[$honest][$j] - 1, $honests))
                || ($y_arr[$honest][$j] == 0 && in_array($x_arr[$honest][$j] - 1, $honests))
            ) {
                $flg = false;
                break 2;
            }
        }
    }

    if ($flg) {
        $max = max($max, count($honests));
    }
}

echo $max;


Measured memory_bytes: 4604
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector <pair<int, int> > ar(n);
	for (int i = 0; i < n; ++i) {
		cin >> ar[i].first;
		ar[i].second = i;
	}
	vector <int> ans(n);
	sort(ar.begin(), ar.end());
	for (int i = 0; 2 * i < n; ++i) {
		ans[ar[i].second] = ar[n / 2].first;
	}
	for (int i = n / 2; i < n; ++i) {
		ans[ar[i].second] = ar[n / 2 - 1].first;
	}
	for (int it: ans) {
		cout << it << endl;
	}
}

Measured memory_bytes: 4608
from fractions import gcd

def primes(N):
    p = [False, False] + [True] * (N - 1)
    for i in range(2,int(N ** 0.5) + 1):
        if p[i]:
            for j in range(i * 2, N + 1, i):
                p[j] = False
    return [i for i in range(N + 1) if p[i]]

def prime_factors(N):
    ret = []
    for p in primes(int(N ** 0.5) + 1):
        while N % p == 0:
            ret.append(p)
            N //= p
    if N > 1:
        ret.append(N)
    return ret
    
a, b = map(int, input().split())
g = gcd(a, b)
print(len(set(prime_factors(g))) + 1)

Measured memory_bytes: 20600
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
A = [LIST() for i in range(N)]
C = [LIST() for i in range(M)]
L = []
for i in range(N):
    index = 0
    mi = INF
    for j in range(M):
        a, b = A[i][0], A[i][1]
        c, d = C[j][0], C[j][1]
        m = abs(a - c) + abs(b - d)
        if mi > min(mi, m):
            mi = min(mi, m)
            index = j
    L.append(index)
for l in L:
    print(l+1)





Measured memory_bytes: 5196
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(long long i=0;i<(long long)(n);i++)
#define N 200000


int main() {
	long long a[N];
	long long b[N];
	long long c[10];
	f(i, 10)c[i] = 0;
	set<pair<long long,long long> >s;
	set<pair<long long, long long> >u;
	f(i, N)a[i] = 0;
	long long n, k;
	long long x, y, z, xx, yy;
	scanf("%lld %lld %lld", &xx, &yy ,&n);
	f(i, n) {
		scanf("%lld %lld", &a[i], &b[i]);
		a[i]--;
		b[i]--;
		s.insert(make_pair(a[i], b[i]));
	}
	c[0] = (xx - 2)*(yy - 2);
	f(i, n) {
		for (long long ii = -2; ii < 3; ii++) {
			for (long long jj = -2; jj < 3; jj++) {
				x = a[i] + ii;
				y = b[i] + jj;
				if ((x >= 0) && (y >= 0) && ((x + 2) < xx) && ((y + 2) < yy)) {
					if (u.count(make_pair(x, y)) == 0) {
						k = 0;
						f(iii, 3) {
							f(jjj, 3) {
								if (s.count(make_pair(x + iii, y + jjj)) == 1)k++;
							}
						}
							c[0]--;
							c[k]++;
						u.insert(make_pair(x, y));
					}
				}
			}
}
	}
	f(i,10)printf("%lld\n", c[i]);


	return 0;
}

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

int count2( int i );

int main( void )
{
  int N;
  cin >> N;
  int max = -INT_MAX;
  int count;
  int maxi;
  for( int i = 1; i <= N; i++ ) {
    count = count2( i );
    //cout << count << endl;
    if( count > max ) {
      max = count;
      maxi = i;
    }
  }

  cout << maxi << endl;
}

int count2( int i )
{
  int count = 0;
  while( 1 ) {
    if( i % 2 == 0 ) {
      count++;
      i /= 2;
    }
    else
      break;
  }
  return count;
}

Measured memory_bytes: 3552
import random
import time

def down_score(d, c, last_d, score):
    sum = 0
    for i in range(26):
        sum = sum + c[i]*(d-last_d[i])
        
    return int(score - sum)


def main():
    D = int(input())

    c = list(map(int, input().split()))

    s = [list(map(int, input().split())) for i in range(D)]

    start = time.time()
    
    last_d = [0 for i in range(26)]
    
    ans = []
    
    score1 = 0
    
    for i in range(D):
        max = 0
        idx = 0
        for j in range(26):
            if max < (s[i][j] + c[j] * (i-last_d[j])*(i-last_d[j]+1)/2) and c[j] != 0:
                max = s[i][j] + c[j] * (i-last_d[j])*(i-last_d[j]+1)/2
                idx = j
            elif max == (s[i][j] + c[j] * (i-last_d[j])*(i-last_d[j]+1)/2) and c[j] * (i-last_d[j])*(i-last_d[j]+1)/2 > c[idx]* (i-last_d[idx])*(i-last_d[idx]+1)/2 and c[j] != 0:
                idx = j
            
        last_d[idx] = i+1
        score1 += s[i][j]
        score1 = down_score(i+1,c,last_d,score1)
        
        ans.append(idx)

    random.seed(0)
    while time.time() - start < 1.9:
        last_d = [0 for i in range(26)]
        score2 = 0  
        tmp1 = 0
        tmp2 = 1
        tmp3 = 2
        if random.randint(0,1):           
            d1 = random.randint(0,D-15) 
            d2 = random.randint(d1+1,d1+7)
            d3 = random.randint(d2+1,d2+7) 
            tmp1 = ans[d1]
            tmp2 = ans[d2]
            tmp3 = ans[d3]
            ans[d1] = tmp2
            ans[d2] = tmp1
            ans[d3] = tmp3
                  
        else:
            d1 = random.randint(0,D-15) 
            d2 = random.randint(d1+1,d1+7)
            d3 = random.randint(d2+1,d2+7) 
            tmp1 = ans[d1]
            tmp2 = ans[d2]
            tmp3 = ans[d3]
            if random.randint(0,1):
                ans[d1] = tmp2
                ans[d2] = tmp3
                ans[d3] = tmp1
            else:
                ans[d1] = tmp3
                ans[d2] = tmp1
                ans[d3] = tmp2
            
        for i in range(D):
            score2 += s[i][ans[i]-1]
            last_d[ans[i]-1] = i+1
            score2 = down_score(i+1, c, last_d, score2)
        
        if score1 > score2:
            ans[d1] = tmp1
            ans[d2] = tmp2
            ans[d3] = tmp3
        else:
            score1 = score2
    
    for i in range(D):
        print(ans[i]+1)  

if __name__ == "__main__":
    main()


Measured memory_bytes: 9768
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>
 
#define mp make_pair
#define pb push_back
 
 
typedef long long ll;
typedef long double ld;
 
using namespace std;
 
int n, m;
vector<int> eds[120000];
int was[120000];
int cl[120000];
int gl;
 
void dfs1(int v, int c) {
	cl[v] = c;
	was[v] = 1;
	for (int u: eds[v]) {
		if (!was[u]) {
			dfs1(u, c ^ 1);
		}
		else {
			if (cl[u] != (cl[v] ^ 1))
				gl = 1;
		}
	}
}
 
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		--a, --b;
		eds[a].push_back(b);
		eds[b].push_back(a);
	}
	ll c0 = 0;
	ll c1 = 0;
	ll c2 = 0;
	for (int i = 0; i < n; ++i) {
		if (was[i])
			continue;
		if (eds[i].empty()) {
			++c2;
			continue;
		}
		gl = 0;
		dfs1(i, 0);
		if (gl)
			++c0;
		else
			++c1;
	}
	ll ans = 0;
	ans += c2 * n + (n - c2) * c2;
	ans += c1 * c1 * 2;
	ans += c0 * c0 + c0 * c1 + c1 * c0;
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 10880
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

const string t[] = {"dream","dreamer","erase","eraser"};
string s;
bool dfs(int i = 0){
  if(i==s.size()) return true;
  bool res = false;
  for(const string& ti:t){
    if(i+ti.size()>s.size()) continue;
    string si = s.substr(i,ti.size());
    if(si!=ti) continue;
    if(dfs(i+si.size())) return true;
  }
  return false;
}
int main() {
  cin >> s;
  cout << (dfs()?"YES":"NO") << endl;
}


Measured memory_bytes: 5848
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; --i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define repc2(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define inf 2e9
#define linf 9000000000000000000ll
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int q;
char str[100'002], s1[200'005], s2[200'005];
bool rev = false;

int main() {
    scanf("%s", str);
    scanf("%d", &q);
    int c, f;
    char ch;
    int len1 = 0, len2 = 0;
    rep(i, q) {
        scanf("%d", &c);
        if (c == 1) {
            rev = !rev;
        } else if (c == 2) {
            scanf("%d %c", &f, &ch);
            if (f == 1) {
                if (!rev) {
                    s1[len1++] = ch;
                    s1[len1] = '\0';
                } else {
                    s2[len2++] = ch;
                    s2[len2] = '\0';
                }
            } else {
                if (rev) {
                    s1[len1++] = ch;
                    s1[len1] = '\0';
                } else {
                    s2[len2++] = ch;
                    s2[len2] = '\0';
                }
            }
        }
    }
    string ans;
    if (!rev) {
        reverse(s1, s1 + len1);
        ans = string(s1) + string(str) + string(s2);
    } else {
        reverse(s2, s2 + len2);
        reverse(str, str + strlen(str));
        ans = string(s2) + string(str) + string(s1);
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1348
import java.util.Scanner;

/**
 * Main
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String N = sc.next();

        if(N.contains("7")){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }

    }
}

Measured memory_bytes: 26952
from itertools import permutations
def dist(x,y):
    return ((x[0]-y[0])**2+(x[1]-y[1])**2)**0.5
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
cnt = 0
for z in permutations(range(N),N):
    for i in range(1,N):
        cnt += dist(X[z[i]],X[z[i-1]])
k = 1
for i in range(2,N+1):
    k = k*i
print(cnt/k)

Measured memory_bytes: 74508
#include   <bits/stdc++.h>
#include   <stdlib.h>
#include   <stdio.h>
#define    pb push_back
#define    mp make_pair
#define    ii   int
#define    ll  long long
#define    pii  pair<ii,ii>
#define    pll  pair<ll,ll>
#define    vcii   vector<ii>
#define    vcll   vector<ll>
#define    vcd     vector<double>
#define    vpii   vector<pair>
#define    scll(x)  scanf("%lld",x)
#define    pfll(x) printf("%lld\n",x)
#define    scd(x) scanf("%llf",x)
#define    pfd(x) prinf("%0.5llf\n",x)
#define pie acos(-1)

using namespace std;
ll Bigmod(ll a,ll b,ll m);
vector<ii> sieve(int n);
void divisor(int n);
void coprime(ll n);
ll gcd(ll a,ll b);
int p[10000],m[1000];

int main()
{

    ll n,a,b,m,sum=0,i;
    cin>>n;
     map<ll,ll>mm;
    for(i=1;i<n;i++)
    {
        cin>>a;
         mm[a]++;

    }
   for(i=1;i<=n;i++)
   {
       cout<<mm[i]<<endl;
   }
    return 0;
}


/*void divisor(int n)
{
      vcii divi[n+1];

      for(int i=1;i<=n;i++)
      {
        for(int j=i;j<=n;j+=i)
        {
          divi[j].pb(i);
        }
      }
    for(int i=1;i<=n;i++)
    {
       for(int j=0;j<divi[i].size();j++)
       {
         cout<<divi[i][j]<<" ";
       }
       cout<<endl;
    }
}
*/

/*vector<ii> sieve(int n)
{
    vci prime;
    map<int,bool>mm;
    int i,j;
    for(i=4; i<=n; i+=2)
        mm[i]=true;
    prime.pb(2);
    for(i=3; i<=n; i+=2)
    {
        if(!mm[i])
        {
            prime.pb(i);

            if(i<=sqrt(n)+2)
            {
                for(j=i*i; j<=n; j+=(i*2))

                {
                    mm[j]=true;

                }
            }
        }
    }
    return prime;
}*/
/*
ll gcd(ll a ,ll b)
{
    if(a==0) return b;

    return gcd(b%a,a);


}
*/
/*

void coprime(ll n)
{
    ll i,j;

    ll p[n+1];
    map<ll,bool>m;
    for(i=1;i<=n;i++)p[i]=i;
    for(i=2;i<=n;i+=2)
    {
        if(i!=2)
        {
            m[i]=1;

        }
        p[i]=p[i]/2;
    }
    p[1]=1;
    m[1]=1;
    for(i=3;i<=n;i+=2)
    {
        if(!m[i])
        {
            p[i]=p[i]-1;
            for(j=i*2;j<=n;j+=i)
            {
                m[j]=1;
                p[j]=p[j]/i*(i-1);
            }

        }
    }

    for(i=1;i<=n;i++)
    {
        cout<<p[i]<<"\n";
    }



}

*/
/*
ll Bigmod(ll a,ll b,ll m)
{
    if(b==0) return 1%m;

    ll x=Bigmod(a,b/2,m);
    x=(x*x)%m;

    if(b%2==1)  x=(x*a)%m;

    return x;
}

*/


Measured memory_bytes: 16124
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int main()
{
    int N, M; cin >> N >> M;
    vector<vector<pair<int, int>>> G(N);
    for (int i = 0; i < M; i++) {
        int u, v, s; cin >> u >> v >> s; u--, v--;
        G[u].emplace_back(v, s);
        G[v].emplace_back(u, s);
    }
    Int xmin = 1, xmax = 1e18;
    vector<bool> visited(N);
    vector<Int> A(N), B(N);
    auto recur = [&](auto rec, int node, Int a, Int b) -> void {
        if (!visited[node]) {
            A[node] = a;
            B[node] = b;
            visited[node] = true;
        } else {
            if (A[node] == a && B[node] != b) {
                xmin = 1e18, xmax = 0;
            } else if (A[node] != a) {
                Int x = (B[node]-b)/(a-A[node]);
                xmin = max(xmin, x);
                xmax = min(xmax, x);
            }
            return;
        }
        if (a > 0) {
            xmin = max(xmin, 1-b);
        } else {
            xmax = min(xmax, -(1-b));
        }
        for (auto &p : G[node]) {
            int next, sum; tie(next, sum) = p;
            rec(rec, next, -a, sum-b);
        }
    };
    recur(recur, 0, 1, 0);
    cout << max(0LL, xmax - xmin + 1) << endl;
    return 0;
}

Measured memory_bytes: 13952
//的場梨沙★担当
//結城晴★副担当
//日野茜★副担当
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string.h>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <cctype>
#include <complex>
#include <regex>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <stdio.h>


using namespace std;

int main(void) {
    double T,X;
    cin>>T>>X;

    cout<<T/X<<endl;
}


Measured memory_bytes: 256
use std::cmp::max;
use std::io::{stdin, Read, StdinLock};
use std::str::FromStr;

struct Input {
    n: usize,
    abc: Vec<Vec<i32>>,
}

fn read_input(cin_lock: &mut StdinLock) -> Input {
    let n = next_token(cin_lock);
    let abc = (0..n)
        .map(|_| (0..3).map(|_| next_token(cin_lock)).collect())
        .collect();
    Input { n, abc }
}

fn solve(input: Input) {
    let mut dp = vec![vec![0; 3]; input.n + 1];

    for i in 0..input.n {
        for j in 0..3 {
            for k in 1..3 {
                let jk = (j + k) % 3;
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][jk] + input.abc[i][jk]);
            }
        }
    }
    println!("{}", dp[input.n].iter().max().unwrap());
}

fn next_token<T: FromStr>(cin_lock: &mut StdinLock) -> T {
    cin_lock
        .by_ref()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>()
        .parse::<T>()
        .ok()
        .unwrap()
}

fn main() {
    let cin = stdin();
    let mut cin_lock = cin.lock();
    let input = read_input(&mut cin_lock);
    solve(input);
}


Measured memory_bytes: 12876
while True :
    n = int(input())
    if n == 0 :
        break
    
    lst = list(map(int, input().split()))
    ave_lst = sum(lst) / len(lst)
    Sum = 0
    for i in range(n) :
        if lst[i] <= ave_lst :
            Sum += 1
    print(Sum)


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

using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '('; __print(x.first); cerr << ','; __print(x.second); cerr << ')';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  string s, t; cin >> s >> t;
  int ans = INT_MAX;
  for (int i = 0; i + t.size() <= s.size(); i++) {
    int cnt = 0;
    string sub = s.substr(i, (int) t.size());
    debug(sub);
    for (int i = 0; i < (int) t.size(); i++) {
      if (sub[i] != t[i]) cnt++;
    }
    ans = min(ans, cnt);
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
//#pragma GCC optimize "-O3"
typedef unsigned long long ull;
typedef unsigned int ui;
typedef unsigned short us;
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll infll=(1ull<<63)-1,mod=1e9+7;
const int inf=(1ull<<31)-1;
int m1,d1,m2,d2;

int main()
{
	//freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(false); cin.tie(0);cout.precision(18);
	cin>>m1>>d1>>m2>>d2;
	if (m1!=m2)
		cout<<"1";
	else 
		cout<<"0";
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

/*
*/

ll n;
ll largest=0;
map<string,int> m;

void init(){
	cin>>n;
	rep(i,n){
		string s;
		cin>>s;
		m[s]++;
	}
}

int main(void){
	init();
	for(auto itr=m.begin(); itr!=m.end(); itr++){
		if(itr->second>largest){
			largest=itr->second;
		}
	}
	// cerr<<"--"<<endl;
	for(auto itr=m.begin(); itr!=m.end(); itr++){
		if(itr->second==largest){
			cout<<itr->first<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 25216
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1e6+5;
int main() {
    string s;cin>>s;
    ll sum=0;
    for(auto x:s) sum+=x-'0';
    if(sum%9) puts("No");
	else puts("Yes");
    return 0;
}

Measured memory_bytes: 3668
(let ((s (read-line)))
  (princ (if (and (char= (char s 0) #\A)
                  (= 1 (count #\C s :start 2 :end (1- (length s)) :test #'char=))
                  (not (some #'upper-case-p
                             (remove #\C (subseq s 1) :test #'char= :count 1))))
             "AC"
             "WA")))

Measured memory_bytes: 3936
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

#define LL long long

int a;
string ch;

int main() {
    scanf("%d",&a);
    cin>>ch;
    if(a >= 3200) cout<<ch;
    else puts("red");
    //system("pause");
    return 0;
}

Measured memory_bytes: 256
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
from re import split
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy
import re

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, m = LI()
X = LI()
D = defaultdict(lambda:defaultdict(int))
for k in X:
    D[k % m][k] += 1

ans = 0
if m % 2 == 0:
    ans += sum(D[m // 2].values()) // 2

ans += sum(D[0].values()) // 2

for i in range(1, (m + 1) // 2):
    x = D[i].values()
    y = D[m - i].values()
    if sum(x) > sum(y):
        x, y = y, x
    x_sum = sum(x)
    y_sum = sum(y)
    ans += x_sum
    ret = 0
    for j in y:
        ret += j // 2 * 2
        if ret > y_sum - x_sum:
            ans += (y_sum - x_sum) // 2
            break
    else:
        ans += ret // 2

print(ans)








Measured memory_bytes: 89496
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

const int INF = 1e+8;
// テ・ツ?・テ・ツ環?
int HP, w, h;
// a[y][x] := (x,y)テ」ツ?ョテ」ツつーテ」ツδェテ」ツδε」ツδ嘉」ツ?ョテァツ環カテヲツ??テヲツ鳴?・ツュツ?A' - 'Z')
vector<string> a;
// D[c] := テヲツ鳴?・ツュツ?c テ」ツ?ォテ・ツッツセテ・ツソツ愿」ツ?凖」ツつ凝・ツ渉療」ツ?妥」ツつ凝」ツδ?」ツδ。テ」ツδシテ」ツつクテヲツ閉ー
int D[256] = {0};

// f[c] := テヲツ鳴?・ツュツ?c ('U','D','L','R') テ」ツ?ォテ・ツッツセテ・ツソツ愿」ツ?凖」ツつ凝・ツ青妥」ツ??0..3 テ」ツつ津ィツソツ氾」ツ??
int f[256] = {0};
// 4ティツソツ妥・ツつ?
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
// dp[k][bits] := k テ・ツ崢榲ァツ崢ョテ」ツ?ョテァツァツサテ・ツ仰陛」ツ?ァテァツ渉セテ・ツ慊ィテ」ツ?ョテ、ツスツソテ」ツ?」テ」ツ?淌」ツδ敕」ツδシテ」ツつキテ」ツδァテ」ツδウテ」ツ?ョテァツ環カテヲツ??bits テ」ツ?ョテ」ツ?ィテ」ツ?催」ツ?ョテヲツ慊?・ツ、ツァテ」ツ?ョテヲツョツ凝」ツつ?HP
int dp[1001][1<<12];

int main(){
	f['U'] = 0; f['D'] = 1; f['L'] = 2; f['R'] = 3;
	int hp;
	
	while( cin >> hp >> HP, hp || HP ){
		cin >> h >> w;
		a = vector<string>(h);
		for(int y=0 ; y < h ; y++ ){
			cin >> a[y];
		}
		int T, S, P;
		cin >> T;
		for(int i=0 ; i < T ; i++ ){
			char c;
			int d;
			cin >> c >> d;
			D[c] = d;
		}
		cin >> S;
		// path[k] := k テ・ツ崢榲ァツ崢ョテ」ツ?ョテァツァツサテ・ツ仰陛」ツ?凖」ツつ凝ヲツ鳴ケテ・ツ青?
		vector<int> path;
		for(int i=0 ; i < S ; i++ ){
			char dir;
			int n;
			cin >> dir >> n;
			for(int j=0 ; j < n ; j++ ){
				path.push_back( f[dir] );
			}
		}
		cin >> P;
		vector<int> p(P);
		for(int i=0 ; i < P ; i++ ){
			cin >> p[i];
		}
		// テ・ツ青?」ツつケテ」ツδ?」ツδε」ツδ療」ツ?ァテ、ツスツ陛」ツδ?」ツδ。テ」ツδシテ」ツつクテ・ツ渉療」ツ?妥」ツつ凝」ツ?凝ィツィツ暗ァツョツ?
		vector<int> damege;
		int x=0, y=0;
		damege.push_back(0);
		for(int i=0 ; i < path.size() ; i++ ){
			x += dx[path[i]];
			y += dy[path[i]];
			damege.push_back( D[a[y][x]] );
		}
		
		// dp テ」ツ?ョテ・ツ按敕ヲツ慊淌・ツ個?
		int N = path.size() + 1;
		for(int i=0 ; i < N ; i++ ){
			for(int j=0 ; j < (1<<P) ; j++ ){
				dp[i][j] = 0;
			}
		}
		dp[0][0] = hp;
		
		for(int i=0 ; i < N ; i++ ){
			for(int j = 0 ; j < (1<<P) ; j++ ){
				if( i > 0 ){ // i テ・ツ崢榲ァツ崢ョテ」ツ?ョテァツァツサテ・ツ仰陛」ツ?ァテ・ツ渉療」ツ?妥」ツ?淌」ツδ?」ツδ。テ」ツδシテ」ツつクテ」ツつ津ィツィツ暗ァツョツ?
					dp[i][j] = max(dp[i][j], dp[i-1][j] - damege[i]);
				}
				// HP テ」ツ??0 テ、ツサツ・テ、ツクツ凝」ツ?ョテ」ツ?ィテ」ツ?催」ツ?ッテァツオツづ、ツコツ?
				if( dp[i][j] <= 0 ) continue;
				
				for(int k=0 ; k < P ; k++ ){
					if( j & (1<<k) ) continue;
					
					// p[k] テ」ツ?ョテ」ツδ敕」ツδシテ」ツつキテ」ツδァテ」ツδウテ」ツつ津、ツスツソテ」ツ??
					int next = j | (1<<k);
					dp[i][next] = min(HP, max(dp[i][next], dp[i][j] + p[k]));
				}
			}
		}
		int ans = 0;
		for(int i=0 ; i < (1<<P) ; i++ ){
			ans = max(ans, dp[N-1][i]);
		}
		cout << (ans? "YES" : "NO") << endl;
	}
}

Measured memory_bytes: 17276
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const long long INF = 1e15;

const int Max = 1e7;
vector<int> mps(Max+1);

void mpsinit(){//O(NloglogN)
    for(int i = 0; i <= Max; i++) mps[i] = i;
    for(ll i = 2; i*i <= Max; i++){
        if(mps[i] == i){
            for(ll j = i*i; j <= Max; j += i){
                if(mps[j] == j) mps[j] = i;
            }
        }
    }
}
template<typename T>
unordered_set<T> prime_factorization(T n){//O(logN)
    unordered_set<T> ret;
    while(mps[n] != n){
        ret.insert(mps[n]);
        n = n/mps[n];
    }
    ret.insert(mps[n]);
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    mpsinit();
    map<int,bool> seen;
    bool pc = true;

    for(int i = 0; i < n; i++){
        if(a[i] == 1) continue;
        unordered_set<int> fp = prime_factorization(a[i]);
        for(auto p:fp){
            if(seen[p]) pc = false;
            seen[p] = true;
        }
    }

    int g = __gcd(a[0],a[1]);
    for(int i = 0; i < n; i++) g = __gcd(g,a[i]);

    if(pc) cout << "pairwise coprime" << endl;
    else if(g == 1) cout << "setwise coprime" << endl;
    else cout << "not coprime" << endl;
}

Measured memory_bytes: 49864