akhauriyash/Code-Regression huggingface dataset:
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Sagor
 */

#include <fstream>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

class Echo {
public:
	void solve(std::istream& in, std::ostream& out) {
	    int n;
	    in>>n;
	    string s;
	    bool c = true;
	    in>>s;
	    //int l = s.size();
	    if(n%2!=0)
	        out<<"No"<<endl;
        else
        {
            for(int i =0;i<n/2;i++)
            {
                if(s[i]!=s[(n/2)+i])
                {
                    out<<"No"<<endl;
                    c = false;
                    break;
                }
            }
            if(c)
                out<<"Yes"<<endl;
        }

	}
};


int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
	Echo solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

using namespace std;


int main()
{
	int r, g, b, n;
	cin >> r >> g >> b >> n;
	int answer = 0;
	for (int i = 0; i <= n; i += r) {
		for (int j = 0; i + j <= n; j += g) {
			if ((n - i - j) % b == 0) answer++;
		}
	}

	cout << answer << endl;
    return 0;
}


Measured memory_bytes: 256
n, m = gets.chomp.split(" ").map {|item| item.to_i }

max_l = 0
min_r = n


m.times do
    l, r = gets.chomp.split(" ").map {|item| item.to_i }
    if l > max_l
        max_l = l
    end
    if r < min_r
        min_r = r
    end
end

if (min_r - max_l) >= 0
    puts (min_r - max_l) + 1
else
    puts "0"
end

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
   	
int main() {
	int n;

	cin >> n;
	vector<tuple<string, int, int> > v; 

	for (int i = 0; i < n; i++)
	{
		string s;
		int p;

		cin >> s;
		cin >> p;
		v.push_back(make_tuple(s, -p, i+1));
	}

	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++)
	{
		cout << get<2>(v[i]) << 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 FOR(i, a, b) for (int i = (a); i < (b); ++i)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
int main() {
  int A, B;
  cin >> A >> B;
  if (A % 3 == 0 || B % 3 == 0 || (A + B) % 3 == 0) {
    puts("Possible");
  } else {
    puts("Impossible");
  }
}

Measured memory_bytes: 256
#include<stdio.h>

long get_gcd(int a, int b){
  long m,n,tmp;
  if(a<b){
    m = a;
    n = b;
  }else{
    m = b;
    n = a;
  }

  do{
    tmp = n;
    n = m % n;
    m = tmp;
  }while(n!=0);


  return m;
}

int main(){
  long n,m,l,gcd;
  long sstep,tstep,j=0;
  char s[100010],t[100010];

  scanf("%ld %ld", &n,&m);
  scanf("%s", s);
  scanf("%s", t);

  gcd = get_gcd(n,m);
  l = gcd*(n/gcd)*(m/gcd);
  sstep = l / m;
  tstep = l / n;

  if(n>m){
    for(int i=0;i<n;i+=sstep){
      if((s[i]!=t[j])&&(t[j]!='\0')){
        l = -1;
        printf("%ld\n", l);
        return 0;
      }
      j+=tstep;
    }
  }else{
    for(int i=0;i<m;i+=tstep){
      if((t[i]!=s[j])&&(s[j]!='\0')){
        l = -1;
        printf("%ld\n", l);
        return 0;
      }
      j+=sstep;
    }
  }

  printf("%ld\n", l);

  return 0;
}

Measured memory_bytes: 384
import logging

logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.disable(logging.CRITICAL)

def main():
    M, D = map(int, input().split())
    
    counter = 0
    for i in range(10, D + 1):
        d1 = i % 10
        d2 = int(i // 10)
        
        
        if d1 >= 2 and d2 >= 2 and d1 * d2 <= M:
            logging.info(str(d1) + " " + str(d2))
            counter += 1
            

    
    print(counter)
    
    logging.info("Hello!")

    
    
    
if __name__ == "__main__":
    main()


Measured memory_bytes: 4212
#include<stdio.h>

int n;
int partition(int *,int,int);
int main(){

  int i,q;
  int A[100000];

  scanf("%d",&n);

  for(i=0;i<n;i++)scanf("%d",&A[i]);

 q=partition(&A[0],0,n-1);

  for(i=0;i<q;i++)printf("%d ",A[i]);
  printf("[%d] ",A[i]);
  for(i=q+1;i<n-1;i++)printf("%d ",A[i]);
  printf("%d\n",A[i]);

  return 0;
}

int partition(int* A,int p,int r){

  int i,j,temp,x;
  
  x=A[r];
  i=p-1;

  for(j=p;j<r;j++){
    if(A[j]<=x){
      i++;
      temp=A[i];
      A[i]=A[j];
      A[j]=temp;
    }
  }
    temp=A[i+1];
    A[i+1]=A[r];
    A[r]=temp;
    return i+1;
}



Measured memory_bytes: 2128
x,n = map(int,input().split())
if n == 0:
    print(x)
else:
    p = list(map(int,input().split()))

    for i in range(n+2):
        if x-i in p:
            if x+i in p:
                a =0
            else:
                print(x+i)
                exit(0) 
        else:
            print(x-i)
            exit(0)



Measured memory_bytes: 9192
/*------------------------------------
........Bismillahir Rahmanir Rahim....
..........created by Abdul Aziz.......
------------------------------------*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#define   mod  998244353
#define   int  long long 
#define   ld   long double
#define   pb   push_back
#define   vi  vector<int> 
#define   dbg(x)  cerr << #x << " = " << x << '\n'
#define   sz(x)  (int)x.size()
#define   all(a) (a.begin(),a.end())
#define   ff   first
#define   ss   second
#define   pii  pair<int,int> 
#define   lcm(a,b) (a*b)/__gcd(a,b) 
using namespace std;

inline void solve(){
    string s,a,b;
    cin >> s ; 
    int n=sz(s); 
    bool ok=true;
    int ans=0;
    for (int i=0,j=n-1;i<j;){
        if (s[i]==s[j]) i++,j--;
        else {
            if (s[i] != 'x' and s[j] != 'x') {
                ok=false;
                break;
            }
            i += (s[i]=='x');
            j -= (s[j]=='x');
            ans++;
        }
    }
    cout << ((ok)?ans:-1) << endl;
}

signed main()
{
    int n=1; // cin>>n;
    while (n--) solve();
    return 0;
}


Measured memory_bytes: 3792
#include <iostream>

using std::cin;
using std::cout;
using std::endl;

int main(void) {
	int x,y,s;

	cin >> x;
	cin >> y;
	cin >> s;

	while (x!=0||y!=0||s!=0) {
		int s1,s2,s3;
		int r,r_M = 0;
		for (s1 = 1; s1 < (s/2)+1; s1++) {
			for (s2 = 1; s2 < s; s2++) {
				s3 = (((s1*(100+x))/100)+((s2*(100+x))/100));
				if (s3==s) {
					r = (((s1*(100+y))/100)+((s2*(100+y))/100)); 
					if (r > r_M) {
						r_M = r;
					}
				}
			}
		}
		cout << r_M << endl;

		cin >> x;
		cin >> y;
		cin >> s;
	}
	return 0;
}

Measured memory_bytes: 3076
use std::collections::VecDeque;

#[allow(unused_macros)]
macro_rules! get {
    ([$t:ty] ; $n:expr) => {
        (0..$n)
        .map(|_| get!([$t])).collect::<Vec<_>>()
    };
    ($($t:ty),+ ; $n:expr) => {
        (0..$n).map(|_| get!($($t),+)).collect::<Vec<_>>()
    };
    ([$t:ty]) => {
        rl().split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect::<Vec<$t>>()
    };
    ($t:ty) => {
        rl().parse::<$t>().unwrap()
    };
    ($($t:ty),*) => {
        {
            let line =rl();
            let mut iter = line.split_whitespace();
            ($(iter.next().unwrap().parse::<$t>().unwrap()),*)
        }
    };
}
fn rl() -> String {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    line.trim().to_string()
}

fn main() {
    let (n, m) = get!(usize, usize);
    let mut edges = Vec::new();
    let mut v = vec![Vec::new(); n];
    for _ in 0..m {
        let (mut a, mut b) = get!(usize, usize);
        a -= 1;
        b -= 1;
        edges.push((a, b));
        v[a].push(b);
        v[b].push(a);
    }
    //eprintln!("{:?}", v);
    //eprintln!("{:?}", edges);
    let mut ans = 0;
    'outer: for i in 0..m {
        let mut visited = vec![false; n];
        let mut q = VecDeque::new();
        q.push_back(0);
        //eprintln!("edges[{}]: {:?}", i, edges[i]);
        while !q.is_empty() {
            let now = q.pop_front().unwrap();
            visited[now] = true;
            for j in 0..v[now].len() {
                let next = v[now][j];

                if (edges[i].0 == now && edges[i].1 == next)
                    || (edges[i].1 == now && edges[i].0 == next)
                {
                    continue;
                }
                //eprintln!("now: {}, next: {}", now, next);
                if visited[v[now][j]] == true {
                    continue;
                }
                q.push_back(v[now][j]);
            }
        }
        //eprintln!("edge: {:?}", edges[i]);
        //eprintln!("visited: {:?}", visited);
        for k in 0..n {
            if visited[k] == false {
                ans += 1;
                continue 'outer;
            }
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include"bits/stdc++.h"
using namespace std;
using ll = long long;

int main() {
    const double PI = acos(-1);

    ll N;
    cin >> N;
    vector<double> x(N), y(N);
    for (ll i = 0; i < N; i++) {
        cin >> x[i] >> y[i];
    }

    //iからjへの角度を求める
    //真上が0度で時計回りに計測
    //iから見てi以外の点が全てある180度の中に収まっていたら凸包の頂点になる
    vector<vector<double>> angle(N, vector<double>(N));

    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j < N; j++) {
            if (j == i) {
                continue;
            }

            if (x[j] == x[i]) {
                if (y[j] > y[i]) {
                    angle[i][j] = 0.0;
                } else {
                    angle[i][j] = PI;
                }
            } else if (x[j] > x[i]) {
                double diff_x = x[j] - x[i];
                double diff_y = y[j] - y[i];
                angle[i][j] = acos(diff_y / sqrt(pow(diff_x, 2) + pow(diff_y, 2)));
            } else {
                double diff_x = x[j] - x[i];
                double diff_y = y[j] - y[i];
                double a = acos(diff_y / sqrt(pow(diff_x, 2) + pow(diff_y, 2)));
                angle[i][j] = 2.0 * PI - a;
            }
        }
    }

    vector<double> min_angles(N);
    for (ll i = 0; i < N; i++) {
        double min_angle = INT_MAX;
        for (ll j = 0; j < N; j++) {
            if (j == i) {
                continue;
            }
            //iから見て、jを一番端としてここから全部の点を含めるのに時計回りで何度必要かを計算
            double tmp = 0;
            for (ll k = 0; k < N; k++) {
                if (k == i || k == j) {
                    continue;
                }
                if (angle[i][k] < angle[i][j]) {
                    tmp = max(tmp, angle[i][k] + 2.0 * PI - angle[i][j]);
                } else {
                    tmp = max(tmp, angle[i][k] - angle[i][j]);
                }
            }
            min_angle = min(min_angle, tmp);
        }

        min_angles[i] = min_angle;
    }

    for (ll i = 0; i < N; i++) {
        printf("%.10f\n", max(PI - min_angles[i], 0.0) / (2.0 * PI));
    }
}

Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>

using namespace std;

#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)

using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

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

    int a, b;
    cin >> a >> b;

    cout << a*b << "\n";
}

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

using namespace std;

int main() {
    string S;
    cin >> S;

    bool flag = true;
    for (int i = 0; i < S.length(); i++) {
        if (i % 2 == 0 && S[i] == 'L')
            flag = false;
        if (i % 2 == 1 && S[i] == 'R')
            flag = false;
    }

    if (flag)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <functional>
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
 
int main () {
  int a, b;
  cin >> a >> b;
  int min = a/0.08;
  int max = (b+1)*10;
  int i =min;
  bool f = false;
  while (i < max){
    int c = i * 0.08;
    int d = i * 0.1;
    if (c == a && d == b){
      cout << i;
      f = true;
      break;
    }
    i ++;
  }
  if (!f){
    cout << "-1";
  }
  return 0;
}

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

int main(void){
  int x[3], ans;
  for(int i = 0; i < 3; i++)
    cin >> x[i];
  sort(begin(x), end(x));
  ans = x[2] * 10 + x[1] + x[0];
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 3576
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll long long
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define endl "\n"
#define pi 3.14159265358979323846264338327950288
#define MOD 10000000007
#define INF -100000000000000
#define ordered_set tree<pair< ll int ,ll  int>, null_type,less<pair<ll int, ll int>>, rb_tree_tag,tree_order_statistics_node_update> 
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
using namespace std;
#define lld long double
using namespace __gnu_pbds;
int main()
{
    fast;
   // #ifndef ONLINE_JUDGE
   // freopen("input.txt", "r", stdin);
   // freopen("output.txt", "w", stdout);
   // #endif
   ll int n,k;
   cin>>n>>k;
   ll int i,z=0;
   ll int a[n];
   for(i=0;i<n;i++)
   	cin>>a[i];
   sort(a,a+n);
   for(i=0;i<k;i++)
   	z=z+a[i];
   cout<<z<<endl;
}

Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <algorithm>

#define rep(i, N) for(int (i) = 0; (i) < (N); (i) ++)
typedef long long ll;

using namespace std;

int main(){
    int A, B, C, D, E, F;
    cin >> A >> B >> C >> D >> E >> F;
    int s_ans = 0;
    int ans = 0;
    double p_max = E / 100.0;
    double p_opt = 0.0;

    for(int i = 1; i <= F ; i ++){
        int w = -1;
        for(int a = 0; a * 100 * A <= i; a ++){
            if((i - 100 * a * A) % (100 * B) == 0){
                w = i;
                break;
            }
        }
        if(w == -1){
            // waterは実現不可
            continue;
        }
        // sugarの上限.doubleで計算.
        int s_max = min(int(p_max * w), F - w);
        for(int c = 0; c * C <= s_max; c ++){
            int d = (s_max - (c * C)) / D;
            int s_tmp = d * D + c * C;
            double p_tmp = (double) s_tmp / (double) (w + s_tmp);
            if(p_opt <= p_tmp){
                p_opt = p_tmp;
                ans = s_tmp + w;
                s_ans = s_tmp;
            }
        }
    }
    cout << ans << " " << s_ans << endl;
    return 0;
}
//27 30 6 17 72 2883


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

#define cerr cout
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
typedef long long ll; typedef pair <int, int> ii; typedef vector <int> vi; const int inf = 1e9 + 7;
string to_string(string s) { return '"' + s + '"';}
string to_string(char s) { return string(1, s);}
string to_string(const char* s) { return to_string((string) s);}
string to_string(bool b) { return (b ? "true" : "false");}
template <typename A> string to_string(A);
template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}
template <typename A> string to_string(A v) {bool f = 1; string r = "{"; for (const auto &x : v) {if (!f)r += ", "; f = 0; r += to_string(x);} return r + "}";}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {cerr << " " << to_string(H); debug_out(T...);}
#define pr(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

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

	int n; cin >> n;
	string s; cin >> s;
	vi f(26); for (char ch: s) f[ch-'a']++;
	ll ans = 1;
	for (int i: f) ans = (ans * (i + 1)) % inf;
	cout << (ans-1+inf)%inf;
	
	return 0;
}

Measured memory_bytes: 512
s = input()
s0 = int(s[0])
s1 = int(s[1])
s2 = int(s[2])
s3 = int(s[3])

for i in range(2):
    a = s0
    if i == 0:
        b = s1
        x = '+'
    else:
        b = -s1
        x = ''
        
    for j in range(2):
        if j == 0:
            c = s2
            y = '+'
        else:
            c = -s2
            y = ''
            
        for k in range(2):
            if k == 0:
                d = s3
                z = '+'
            else:
                d = -s3
                z = ''
            
            if a+b+c+d == 7:
                e = [str(a),x,str(b),y,str(c),z,str(d),'=7']
                print(''.join(e))
                exit()

Measured memory_bytes: 3064
// 3 4
// ...#
// .#..
// ....
#include<bits/stdc++.h>
#define ll long long
#define inf 1e12 
#define mo 1000000007
ll dp[1001][1001];
ll mat[1001][1001];
using namespace std;
int main()
{
	ll n,m;
	cin>>n>>m;
	
	for(ll z=0;z<n;z++)
	{
		for(ll w=0;w<m;w++)
		{
			char c;
			cin>>c;
			if(c=='#')
			{
				mat[z][w]=-1;
			}
			else
			{
				mat[z][w]=0;
			}
			dp[z][w]=0;
		}
	}
	dp[0][0]=1;
	for(ll e=1;e<m;e++)
	{
		if(mat[e][0]==-1)
			dp[e][0]=0;
		else
		dp[e][0]=dp[e-1][0];
	}
	for(ll w=0;w<n;w++)
	{
		for(ll z=1;z<m;z++)
		{
			if(mat[w][z]==-1)
			{
				dp[w][z]=0;
				continue;
			}
			
			if(w==0)
			{
				dp[w][z]=dp[w][z-1];
				continue;
			}
			dp[w][z]=(dp[w-1][z]+dp[w][z-1])%mo;
		}
	}
	// for(ll e=0;e<n;e++)
	// {
	// 	for(ll r=0;r<m;r++)
	// 	{
	// 		cout<<dp[e][r]<<" ";
	// 	}
	// 	cout<<endl;
	// }
	cout<<dp[n-1][m-1];
}

Measured memory_bytes: 15872
#include <cstdio>
#include <vector>
#include <tuple>
#include <queue>
#include <map>
using namespace std;

int main() {
	int N, Q;
	scanf("%d%d", &N, &Q)+1;

	//           数値  子リスト
	vector<tuple<int, vector<int>>> tree(N);

	int tmp1, tmp2;
	for (int i = 0; i < N-1; i++) {
		scanf("%d%d", &tmp1, &tmp2)+1;
		get<1>(tree[tmp1-1]).push_back(tmp2-1);
		get<1>(tree[tmp2-1]).push_back(tmp1-1);
	}

	for (int i = 0; i < Q; i++) {
		scanf("%d%d", &tmp1, &tmp2)+1;
		get<0>(tree[tmp1-1]) += tmp2;
	}

	queue<int> que;
	map<int, int> map;

	tmp1 = get<0>(tree[0]);
	int size = get<1>(tree[0]).size();
	for (int j = 0; j < size; j++) {
		get<0>(tree[get<1>(tree[0])[j]]) += tmp1;
		que.push(get<1>(tree[0])[j]);
	}
	map[0] = 1;

	while (que.size() > 0) {
		int target = que.front();
		que.pop();
		tmp1 = get<0>(tree[target]);
		int size = get<1>(tree[target]).size();
		for (int j = 0; j < size; j++) {
			if (map[get<1>(tree[target])[j]] != 1) {
				get<0>(tree[get<1>(tree[target])[j]]) += tmp1;
				que.push(get<1>(tree[target])[j]);
			}
		}
		map[target] = 1;
	}

	for (int i = 0; i < N-1; i++) {
		printf("%d ", get<0>(tree[i]));
	}
 
	printf("%d\n", get<0>(tree[N-1]));
	
	return 0;
}


Measured memory_bytes: 24824
#include<cstdio>
#define RI register int
#define CI const int&
/*  ans:a[2]
	mul:a[3]
	new:a[4]
	a+1:a[5]
	mul':a[6]
	new':a[7]
	pw2[x]:a[8+x]*/
using namespace std;
int cnt=100,rb=100000;
inline void add(CI x,CI y,CI z) { printf("+ %d %d %d\n",x,y,z); }
inline void lower(CI x,CI y,CI z) { printf("< %d %d %d\n",x,y,z); }
inline void mul(CI x,CI y,CI z) // a[z]=a[x]*2^y
{
	++rb; add(rb,x,rb); for (RI i=1;i<=y;++i) add(rb,rb,rb+1),++rb; add(rb+1,rb,z);
}
int main()
{
	puts("73224"); RI i,j; add(0,1,++cnt); lower(cnt+1,cnt,cnt+1);
	++cnt; add(cnt,cnt+1,8); ++cnt;
	for (i=1;i<=60;++i) add(8+i-1,8+i-1,8+i);
	for (add(0,8,5),i=30;~i;--i)
	{
		add(4,8+i,4); lower(4,5,++cnt); int c1=cnt;
		mul(cnt,i,cnt+1); ++cnt; add(3,cnt,3);
		add(3,cnt+1,4); mul(1,i,cnt+1); ++cnt;
		add(cnt,8,cnt+1); ++cnt; int tar=cnt;
		add(cnt+1,cnt+1,6); add(cnt+1,cnt+1,7);
		for (j=60;~j;--j)
		{
			add(7,8+j,7); lower(7,tar,++cnt); int c2=cnt;
			add(c1,c2,++cnt); lower(8,cnt,cnt+1); ++cnt;
			mul(cnt,j,cnt+1); ++cnt; add(cnt,6,6); add(6,cnt+1,7);
		}
		add(2,6,2);
	}
	return 0;
}

Measured memory_bytes: 1836
// 2008ツアツジツアツ地ツ凝ヲツ予ツ選I : Common Polynomial

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int abs(int x){ return x > 0 ? x : -x; }

int gcd(int a, int b){ return a%b ? gcd(b, a%b) : b; }
int lcm(int a, int b){ return a/gcd(a,b)*b; }

vector<int> mul(vector<int> a, vector<int> b){
	vector<int> res(a.size()+b.size()-1, 0);
	for(int i=0;i<a.size();i++)
		for(int j=0;j<b.size();j++)
			res[i+j] += a[i]*b[j];
	return res;
}

vector<int> pow(vector<int> vi, int p){
	vector<int> res(1,1);
	for(int i=0;i<p;i++)
		res = mul(res, vi);
	return res;
}

vector<int> add(vector<int> a, vector<int> b){
	vector<int> res(max(a.size(), b.size()), 0);
	for(int i=0;i<a.size();i++) res[i] += a[i];
	for(int i=0;i<b.size();i++) res[i] += b[i];
	return res;
}

int getDigit(string &str, int &idx){
	int res = 0;
	while(idx<str.size() && isdigit(str[idx]))
		res = 10*res+str[idx++]-'0';
	return res;
}

vector<int> parseExpr(string&, int&);

vector<int> parseFact(string &str, int &idx){
	vector<int> res(1, 0);
	if(isdigit(str[idx])){
		res[0] = getDigit(str,idx);
	} else if(str[idx]=='x') {
		res.push_back(1);
		idx++;
	} else if(str[idx]=='('){
		idx++;
		res = parseExpr(str, idx);
		idx++;
	}
	if(idx < str.size() && str[idx]=='^'){
		idx++;
		res = pow(res, getDigit(str, idx));
	}
	return res;
}

vector<int> parseTerm(string &str, int &idx){
	vector<int> res(1, 1);
	while(idx < str.size() && str[idx]!='-' && str[idx]!='+' && str[idx]!=')')
		res = mul(res, parseFact(str, idx));
	return res;
}

vector<int> parseExpr(string &str, int &idx){
	vector<int> res(1, 0);
	while(idx < str.size() && str[idx]!=')'){
		bool m = (str[idx]=='-');
		if(str[idx]=='-'||str[idx]=='+') idx++;
		vector<int> vi = parseTerm(str, idx);
		if(m) for(int i=0;i<vi.size();i++) vi[i] *= -1;
		res = add(res, vi);
	}
	return res;
}

void normalize(vector<int> &vi){
	while(!vi.empty() && vi.back() == 0) vi.pop_back();
	if(vi.empty()) return ;
	int g = vi.back();
	for(int i=0;i<vi.size();i++)
		if(vi[i]!=0) g = gcd(g, abs(vi[i]));
	for(int i=0;i<vi.size();i++) vi[i] /= g;
	if(vi.back()<0)
		for(int i=0;i<vi.size();i++) vi[i] *= -1;
}

void print(vector<int> vi){
	for(int i=vi.size()-1;i>=0;i--){
		if(vi[i]==0) continue;
		if(i==0||abs(vi[i])>1){
			if(i==vi.size()-1) printf("%d", vi[i]);
			else               printf("%+d", vi[i]);
		} else if(i!=vi.size()-1){
			if(vi[i]>0) printf("+");
			else        printf("-");
		}
		if(i > 0) printf("x");
		if(i > 1) printf("^%d", i);
	}
	puts("");
}

vector<int> gcm(vector<int> a, vector<int> b){
	while(true){
		normalize(a);
		normalize(b);
		if(a.empty()) break;
		int L = lcm(a.back(), b.back());
		if(a.size() < b.size()) swap(a, b);
		a = mul(a, vector<int>(1, L/a.back()));
		b = mul(b, vector<int>(1, L/b.back()));
		for(int idxA = a.size()-1,idxB = b.size()-1;idxA>=0 && idxB>=0;idxA--,idxB--)
			a[idxA] -= b[idxB];
	}
	return b;
}


int main(){
	string str;
	while(cin >> str){
		if(str == ".") break;
		int idx = 0;
		vector<int> a = parseExpr(str, idx);
		cin >> str;
		idx = 0;
		vector<int> b = parseExpr(str, idx);
		print(gcm(a, b));
	}
}

Measured memory_bytes: 0
/*
 *  Language:   C++
 *  Author:     Debajyoti Dasgupta
 */
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

bool check(const vector<pair<int, int>>& a) {
    int cur = 0;
    for (auto i:a) {
        if (cur + i.first < 0) return false;
        cur += i.second;
    }
    return true;
}

int main() {
    int n, total = 0;
    cin >> n;
    vector<pair<int, int>> ls, rs;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        int mn = 0, cur = 0;
        for (char &s1:s) {
            cur += (s1 == '(' ? 1 : -1);
            mn = min(mn, cur);
        }
        total += cur;
        if (cur > 0) {
            ls.emplace_back(mn, cur);
        } else {
            rs.emplace_back(mn - cur, -cur);
        }
    }
    sort(ls.rbegin(), ls.rend());
    sort(rs.rbegin(), rs.rend());
    if (!total && check(ls) && check(rs)) {
        cout << "Yes";
    } else {
        cout << "No";
    }
    return 0;
}


Measured memory_bytes: 11232
#include <iostream>
#include <vector>
#include <numeric>
#include <tuple>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <limits>
#include <unordered_map>
#include <type_traits>
#include <map>
#include <cstdio>
#include <string>

using namespace std;
using str = string;

#define rep(a,l,r) for(int a=(l);a<(r);a++)
#define get cin>>
#define put cout<<

int gcd_euclid(int u, int v) {
  int r;
  while (0 != v) {
    r = u % v; u = v; v = r; /* swap */
  }
  return u;
}

// 最大公約数算出
int calc_gcd(const vector<int> vec){
	int gcd = *min_element(vec.begin(), vec.end());
	for (const int ele: vec){
		gcd = gcd_euclid(gcd,ele);
	}
	return gcd;
}

// 最小公倍数
int calc_lcm(const vector<int> vec) {
	int tmp = 1;
	for (const int ele: vec){
		tmp *= ele;
	}
	int gcd = calc_gcd(vec);
	return tmp/gcd;
}

std::string join(const std::vector<std::string>& v, const char* delim = 0) {
  std::string s;
  if (!v.empty()) {
    s += v[0];
    for (decltype(v.size()) i = 1, c = v.size(); i < c; ++i) {
      if (delim) s += delim;
      s += v[i];
    }
  }
  return s;
}

// nが奇数、偶数の場合の場合分け
// n & 1 ? odd : even

// distinctはsortしてunique + erase
// https://qiita.com/ysk24ok/items/30ae72f4f1060b088588
//sort(vec.begin(), vec.end());
//vec.erase(unique(vec.begin(), vec.end()), vec.end());


// 全パターン列挙
//vector<vector<int>> res;
//
//void exp(int range, int times, vector<int>& vec){
//	if (times == 0){
//		res.push_back(vec);
//		return;
//	}
//	rep(i,0,range){
//		if (find(vec.begin(),vec.end(),i) == vec.end()) {
//			vector<int> tmp{vec};
//			tmp.emplace_back(i);
//			exp(range, times - 1, tmp);
//		}
//	}
//}

str s;

long solve(str exp){
	bool isFirst = true;
	long l = 0;
	str tmp{};

	for(auto c: exp){
		if (c == '+'){
			if (isFirst){
				l = stol(tmp);
				isFirst = false;
			} else {
				l += stol(tmp);

			}
			tmp = "";
			continue;
		}
		tmp += c;
	}

	l += stol(tmp);

	return l;
};

long rec(int i, str exp){
	if(i == (int)s.size()){
		return solve(exp);
	}
	if (exp == ""){
		return rec(i + 1, exp + s[i]);
	} else {
		return rec(i + 1, exp + '+' + s[i]) + rec(i + 1, exp + s[i]);
	}
};

void run() {

	get s;

	put rec(0,"");

}

int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);run();return 0;}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PI 3.1415926535897
using namespace std;
typedef long long ll;
const int INF = 1000000000;
const ll LINF = 1000000000000000000; //1e18
const double EPS = 1e-10;            //

int main(void)
{
    string a, b, c;
    cin >> a >> b >> c;

    a[0] += 'A' - 'a';
    b[0] += 'A' - 'a';
    c[0] += 'A' - 'a';
    cout << a[0] << b[0] << c[0] << endl;

    return (0);
}

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

using namespace std;

#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define endl "\n"
#define trace(x) cerr << #x << ": " << x << " " << endl;

#define sz(a) ( (int) (a).size() )
#define all(v) (v).begin(), (v).end()
#define tr(c, it) for(auto (it) = (c).begin(); (it) != (c).end(); it++)
#define pres(c, val) ((c).find(val) != (c).end()) //
#define cpres(c, val) (find(all(c), val) != (c).end()) //

#define pb push_back
#define mp make_pair
#define F first
#define S second

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

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<int>::iterator vit;

const int N = 1e9 + 7;

void solve() {
    int n;
    cin >> n;
    vi a(n);
    rep(i) cin >> a[i];
    vi b = a;
    sort(all(a));
    map<int, int> f, g;
    rep(i) f[a[i]]++;
    int s = 0;
    tr(f, it) s += ((it->S)*(it->S-1))/2;
    tr(f, it) {
        g[it->F] = s - ((it->S)*(it->S-1))/2 + ((it->S-1)*(it->S-2))/2;
    }
    rep(i) cout << g[b[i]] << endl;
}

int32_t main(int32_t argc, char** argv) {
    fastio;
    solve();
    return 0;
}

Measured memory_bytes: 20480
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[9]={1,0,-1,0,1,1,-1,-1,0};
const ll dx[9]={0,-1,0,1,1,-1,1,-1,0};
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;
}

int main(){
    ll n;cin >> n;
    map<ll,ll> mp;
    vl v(n);
    rep(i,n)cin >> v[i],mp[v[i]]++;
    sort(all(v));
    ll res=0;
    per(i,n){
        if(!mp[v[i]])continue;
        mp[v[i]]--;
        bool check=false;
        per(j,31){
            if((1<<j)-v[i]<=0)break;
            if(mp[(1<<j)-v[i]]){
                check=true;
                res++;
                mp[(1<<j)-v[i]]--;
                break;
            }
        }
        if(!check)mp[v[i]]++;
    }
    cout << res <<endl;
} 

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

int main() {
  vector<char> c(6);
  for (int i = 0; i < 6; i++) cin >> c.at(i);
  if (c.at(0) == c.at(5) && c.at(1) == c.at(4) && c.at(2) == c.at(3)) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
int main() {
  int n;
  cin >> n;
  vector<int> p(n);
  for (int i = 0; i < n; i++) {
    cin >> p.at(i);
  }

  int a = p.at(0);
  int cnt = 0;
  for (auto x: p) {
    if (x <= a) {
      a = x;
      cnt++;
    }
  }

  cout << cnt << endl;
} 

Measured memory_bytes: 1024
a = sorted(list(map(int, input().split())))

ans = a[2] - a[1]
a[0] += a[2] - a[1]
if (a[2] - a[0]) % 2 == 0:
    print(ans + (a[2] - a[0]) // 2)
else:
    print(ans + 2 + (a[2] - a[0]) // 2)

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <math.h>
#include <map>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
#define lli long long int
#define vi vector<int>
#define vlli vector<lli>
#define pii pair<int, int>
#define plli pair <lli, lli>
#define F(i,n) for(lli (i)=0;(i)<(n);(i)++)
#define FR(i,n) for(lli (i)=(n)-1;(i)>=0;(i)--)
#define FSG(i,a,b) for(lli (i)=(a);(i)<(b);(i)++)
#define FSGR(i,a,b) for(lli (i)=(b)-1;(i)>=(a);(i)--)
#define VAL(n) cout << n << endl;
#define VALD(n) cout << #n << ": " << n << endl;

int main(){
  int A, B;
  cin >> A >> B;
  cout << max(A + B, max(A-B, A*B)) << endl;
  return 0;
}


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

using namespace std;

int n,m;
int c[21];
int ans;
int dp[21][50001];
int null = -1;
int inf = 1<<21;

int dfs(int i,int price){
    int res;
    
    if(dp[i][price] != null){
        res = dp[i][price];
        return res;
    }
    else if(price == 0){
        res =  0;
    }
    else if(price < 0  || i == m){
        res = inf;
    }
    else if(price < c[i]){
        res = dfs(i+1,price);
    }
    else if(price > 0){
        res = min(dfs(i+1,price),dfs(i,price-c[i])+1);
    }
    dp[i][price] = res;
    return res;
}

int main(){
    cin >> n >> m;
    for(int i=0;i<m;i++){
        cin >> c[i];
    }
    //sort(c,c+m,greater<>());
    //なぜか上のように降順にソートすると以下のテストケースでacされる、ソートしないと43000回目くらいの再帰(i=0,price=6000くらい(c[i]=1)で唐突に止まる。
    //50000 20
    //1 92 1377 3168 7095 1170 1809 5046 3225 1054 4016 142 108 6430 3970 48 8416 4909 114 6968
    //調べたところメモリのスタック領域が何とか、、ソートするとaｃとなる理由はわからず。
    for(int i=0;i<=m;i++){
        for(int j=0;j<=n;j++){
            dp[i][j] = null;
        }
    }
    ans = dfs(0,n);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 9524
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
const int mod = 1e9+7, N = 20;

int a[N][N], ans = 0, n, m, k;
vector<int> x(20,0);
void check(){
	int c = 0;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(!x[i]&&!x[j+n]){
				c+=a[i][j];
			}
		}
	}if(c == k)ans ++;
}
void rec(int now){
	if(now == n+m){
		check();
		return;
	}else {
		x[now] = 1;
		rec(now+1);
		x[now] = 0;
		rec(now+1);
	}
}
void solve(int test_case){
	int i, j;
	cin >> n >> m >> k;
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			char c;
			cin >> c;
			if(c == '#')a[i][j] = 1;
		}
	}
	rec(0);
	cout << ans;
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int ___T;
	cin >> ___T;
	for(int T_CASE = 1; T_CASE <= ___T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}


Measured memory_bytes: 3640
#最大公約数
def gcd(a,b):
    if a==b:
        return b
    elif a%b == 0:
        return b
    else:
        return gcd(b,a%b)
def lcd(a,b):
    gc = gcd(a,b)
    return (a*b)//gc
N = int(input())
t = []
num = 1
lc = 1
for i in range(N):
    tmp = int(input())
    if tmp not in t:
        t.append(tmp)
t.sort()
for i in range(len(t)):
    tmp = lc
    lc = lcd(t[i],tmp)
print(lc)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define int long long
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using P=pair<long long,long long>;
#define rep(i,n) for(long long i=0; i<(long long)n; i++)
#define FOR(i,a,b) for(long long i=a; i<b; i++)
#define ll long long
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((long long)(x).size())
#define COUT(x) cout << x << endl
#define PB(x) push_back(x)
#define MP make_pair
#define f first
#define s second
#define ld long double
#define vint vector<int>
#define vvint vector<vector<int>>
#define vstr vector<string>
#define vp vector<pair<int,int>>
#define vb vector<bool>
#define SUM(x) accumulate(x.begin(),x.end(),0)
#define MAX(x) *max_element(x.begin(),x.end())
#define MIN(x) *min_element(x.begin(),x.end())
#define couty cout<<'Y'<<'e'<<'s'<<endl
#define coutn cout<<'N'<<'o'<<endl
#define coutY cout<<'Y'<<'E'<<'S'<<endl
#define coutN cout<<'N'<<'O'<<endl
#define yn(x) cout<<(x?"Yes":"No")<<endl
#define YN(x) cout<<(x?"YES":"NO")<<endl
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
const long long dx[4]={1,0,-1,0};
const long long dy[4]={0,1,0,-1};
const long long INF = 1e12;
const long long MOD = 1e9+7;

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(15);

    int n; cin >> n;
    vint p(n),q(n);
    rep(i,n) cin >> p[i];
    rep(i,n) cin >> q[i];
    vint order(n);
    rep(i,n) order[i]=i+1;
    int res=0;
    int count=0;
    do{
        count++;
        if(order==p) res+=count;
        if(order==q) res-=count;
    }while(next_permutation(all(order)));
    cout<<abs(res)<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <map>
#include <cmath>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;

#define rep(i, o) for (ll i = 0; i < (o);i++)
#define rep_s(i, o) for (int i = 1; i <= (o);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<(int)(b);i++)
#define NUM 1e5

typedef long long ll;
typedef unsigned long long ull;

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll c, ll d) { return c / gcd(c, d) * d; }


template<class T>
bool chmax(T &a, const T &b) { if (a < b) { return b; } return a; }

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

int main() {
    char c; 
    cin >> c;

    char ans = 'a';
    if (c >= 'A' && c <= 'Z') ans = 'A';

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

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

// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0000

int main() {
	for (int i = 1; i <= 9; i++)
		for (int j = 1; j <= 9; j++)
			cout << i << "x" << j << "=" << i * j << endl;
	return 0;
}

Measured memory_bytes: 1116
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a,b,c,ans=0;
  cin >> a >> b >> c;
  for(int i = 0;i<a+1;i++){
    int sum = 0;
    int j = i;
    while(j>0){
      sum += j%10;
      j /=10;
    }
    if(sum>=b&&sum<=c)ans+=i;
  }
  cout << ans;
}

Measured memory_bytes: 3604
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
 
import collections
import sys
 
 
def count_connected_components(max_v, adj_list):
    result = 0
    visited = collections.defaultdict(bool)
 
    def depth_first_search(start_v):
        visited[start_v] = True
        for v in adj_list[start_v]:
            if not visited[v]:
                depth_first_search(v)
    for u in range(max_v):
        if not visited[u]:
            depth_first_search(u)
            result += 1
    return result
 
 
def main():
    sys.setrecursionlimit(50000)
    n, m = map(int, input().split())
    adj_list = collections.defaultdict(set)
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        adj_list[a].add(b)
        adj_list[b].add(a)
    print(count_connected_components(n, adj_list) - 1)
 
 
if __name__ == '__main__':
    main()


Measured memory_bytes: 74776
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int A, B, M;
    cin >> A >> B >> M;

    vector<int> a(A), b(B);
    int ma = inf, mb = inf;
    REP(i, A) {
        cin >> a[i];
        ma = min(ma, a[i]);
    }
    REP(i, B){
        cin >> b[i];
        mb = min(mb, b[i]);
    }

    int ans = ma + mb;

    REP(i, M) {
        int x, y, c;
        cin >> x >> y >> c;
        --x; --y;
        ans = min(ans, a[x] + b[y] - c);
    }

    cout << ans << endl;
}


Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<algorithm>	
#include<cmath>
using namespace std;
int main() {
	long long n = 0, a ,b, c = 0, d = 0, e = 0;
	for (int i = 0; i < 3; i++) {
		cin >> a >> b;
		if (a == 1 || b == 1) { n++; }
		if (a == 2 || b == 2) { c++; }
		if (a == 3 || b == 3) { d++; }
		if (a == 4 || b == 4) { e++; }
	}
	if (n == 3 || c == 3 || d == 3 || e == 3) {
		cout << "NO" << endl;
	}
	else { cout << "YES" << endl; }
	cin >> a;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
ls = [0] * n
ans = []
for i in range(n-1, -1, -1):
    t = 0
    for j in range(i, n, (i + 1)):
        t += ls[j]
    if a[i] != t % 2:
        ans.append(i + 1)
        ls[i] = 1
print(len(ans))
if len(ans) != 0:
    print(*ans)


Measured memory_bytes: 14096
#include<stdio.h>

int gcd(int i,int j);

int main() {
  int i,j,k,n;
  long long sum = 0;
  scanf("%d",&n);
  for(i = 1;i <= n;i++) {
    for(j = 1;j <= n;j++) {
      for(k = 1;k <= n;k++) {
        sum += gcd(gcd(i,j),k);
      }
    }
  }
  printf("%lld\n",sum);

  return 0;
}


int gcd(int i,int j) {
  if(i % j == 0) {
    return j;
  } else {
    return gcd(j,i%j);
  }
}


Measured memory_bytes: 1736
#include <iostream>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cassert>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
#include <cmath>
#include <bitset>
#include <functional>
#include <limits>
#include <map>
using namespace std;

typedef long long ll;
#define rep2(i, n) for(ll i = 2; i <=(ll)(n); i++)
#define rep1(i, n) for(ll i = 1; i <=(ll)(n); i++)
#define rep0(i, n) for(ll i = 0; i <=(ll)(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; }

ll pow(ll a, ll n) { //compute a^n with o(logn)
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}

ll pow(ll a, ll n, ll mod) { //compute a^n (mod mod) with o(logn)
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

const int MAX = 199;
const int MOD = 1000000007;
ll fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
ll COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

//順列計算
ll PER(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[n - k] % MOD) % MOD;
}

int main(){
    string s;
    cin >> s;
    int len = s.length();
    if(s[len-1] == 's') cout << s+"es" << endl;
    else cout << s+"s" << endl;
    return 0;
}

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
// make pair, tuple
// __gcd(int, int)
// bool isPrime(int n){
//       if(n <= 1)return false;
//       if(n <= 3)return true;
//       if(n % 2 == 0 || n % 3 == 0)return false;
//       for(int i = 5;i * i <= n;i += 6){
//             if(n % i == 0 || n % (i + 2) == 0)return false;
//       }
//       return true;
// }
// int countSubString(string s, string temp){
//       int ans = 0;
//       size_t f = s.find(temp);
//       while(f != string::npos){
//             ans++;
//             f = s.find(temp, f + 1);
//       }
//       return ans;
// }

int main(){
    int a,b;cin >> a >> b;
    for(int i = 0;i < max(a, b);i++){
        cout << min(a, b);
    }
}

Measured memory_bytes: 256
import Control.Monad
import Data.List
import Data.Maybe
import qualified Data.ByteString.Char8 as B
import Debug.Trace

main :: IO ()
main = do
    [n,m]  <- map (fst . fromJust . B.readInt) . B.words <$> B.getLine
    ns <- replicateM m ((\[a,b]->(a,b)) .
            map (fst . fromJust . B.readInt) . B.words <$> B.getLine)
    print . length . merge . sort $ ns

merge ((a,b):(c,d):ns)
    | a <= c && b <= d && c < b = merge ((c, b):ns)
    | a <= c && d <= b && c < d = merge ((c, d):ns)
    | c <= a && b <= d && a < b = merge ((a, b):ns)
    | c <= a && d <= b && a < d = merge ((a, d):ns)
    | otherwise                  = (a,b) : merge ((c,d):ns)
merge ns = ns


Measured memory_bytes: 49532
import std.stdio, std.string, std.conv, std.algorithm, std.numeric;
import std.range, std.array, std.math, std.typecons, std.container, core.bitop;

int[] di = [1,0,-1,0,1,1,-1,-1], dj = [0,1,0,-1,1,-1,1,-1];
int ans;

void main() {
    while (1) {
        int n;
        scan(n);

        if (!n) return;

        auto ans = cntp(n);
        writeln(ans);
    }
}

int cntp(int n) {
    int cnt;

    foreach (a ; n + 1 .. 2*n + 1) {
        cnt += isPrime(a);
    }

    return cnt;
}

bool isPrime(int a) {
    for (int p = 2; p*p <= a; p++) {
        if (a % p == 0) {
            return false;
        }
    }
    return true;
}


void scan(T...)(ref T args) {
    string[] line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}


void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

Measured memory_bytes: 2436
#include "bits/stdc++.h"
using namespace std;

// GNU C Compiler
//template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

// type
using ll = int_fast64_t;
using ull = uint_fast64_t;
using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
//using pair<T1, T2> = p12;

//container
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
#define ALL(v) v.begin(),v.end()

//repetition
#define REP(n) for(int i=0; i<(n); i++)
#define REPj(n) for(int j=0; j<(n); j++)
#define REPinit(i,a,n) for(int i=(a); i<(n); i++)
#define REPinitj(j,a,n) for(int j=(a); j<(n); j++)

//algorithm
//#define SORT(c) sort((c).begin(),(c).end())

//constant

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//Optimizer
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

/*
    add utility Algorithm
*/


int A[3][3];
int B[3][3];


int main(int argc, char const* argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    REPinit(i, 0, 3) {
        REPinit(j, 0, 3) {
            cin >> A[i][j];
            B[i][j] = 0;
        }
    }

    int N;
    cin >> N;

    int b;
    REPinit(k, 0, N) {
        cin >> b;
        REPinit(i, 0, 3) {
            REPinit(j, 0, 3) {
                if (A[i][j] == b) B[i][j] = 1;
            }
        }
    }


    REPinit(i, 0, 3) {
        if ((B[i][0] + B[i][1] + B[i][2]) == 3) {
            cout << "Yes" << endl;
            return 0;
        }
    }

    REPinit(i, 0, 3) {
        if ((B[0][i] + B[1][i] + B[2][i]) == 3) {
            cout << "Yes" << endl;
            return 0;
        }
    }

    if ((B[0][0] + B[1][1] + B[2][2]) == 3) {
        cout << "Yes" << endl;
        return 0;
    }

    if ((B[0][2] + B[1][1] + B[2][0]) == 3) {
        cout << "Yes" << endl;
        return 0;
    }


    cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 256