akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define nitro ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
#define pb push_back
#define PI 3.1415926535897932384626
#define MOD 1000000007
#define DEBUG false
#pragma GCC optimize "trapv"
 
void solve(int n,int wt[],int val[],int W)
{
    int K[n+1][W+1],i; 
   for (i = 0; i <= n; i++) 
   { 
       for (int w = 0; w <= W; w++) 
       { 
           if (i==0 || w==0) 
               K[i][w] = 0; 
           else if (wt[i-1] <= w) 
                 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]); 
           else
                 K[i][w] = K[i-1][w]; 
       } 
   }
   cout<<K[n][W]<<'\n';
}
int32_t main()
{
    nitro;
    int n,W,x,y;
    cin>>n>>W;
    int wt[n],val[n];
    for(int i=0;i<n;i++)
    {
        cin>>wt[i]>>val[i];
    }
    solve(n,wt,val,W);
return 0;
}

Measured memory_bytes: 79232
from fractions import gcd

def divisors(n, reverse=False):
    table = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            table.append(i)
            if i != n // i:
                table.append(n // i)
    table.sort(reverse=reverse)
    return table

def common_divisors(x, y, reverse=False):
    return divisors(gcd(x, y), reverse=reverse)


a, b = map(int, input().split())

res = 0
for i in common_divisors(a, b):
    for k in range(2, int(i**0.5)+1):
        if i % k == 0:
            break
    else:
        res += 1
print(res)


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

string s[1000];
int h,w,n;
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};

int bfs(int x,int y,int now)
{
	int d[h][w]={};
	queue<pair<int,int>>Q;
	Q.push(make_pair(8,x*1000+y));
	while(!Q.empty())
	{
		pair<int,int>a=Q.front();Q.pop();
		int tx=a.second/1000,ty=a.second%1000;
		if(s[tx][ty]-'0'==now)
		{
			return a.first/10;
		}
		for(int r=0;r<4;r++)
		{
			if(abs(a.first%10-r)==2)continue;
			int sx=tx+dx[r];
			int sy=ty+dy[r];
			if(sx<0||sy<0||sx>=h||sy>=w||s[sx][sy]=='X'||d[sx][sy]!=0)continue;
			Q.push(make_pair((a.first/10+1)*10+r,sx*1000+sy));
			d[sx][sy]=1;
		}
	}
	return 1<<26;
}

int main()
{
	cin>>h>>w>>n;
	for(int i=0;i<h;i++)cin>>s[i];
	int c=0;
	pair<int,int> pr[9];
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			if(s[i][j]=='S')
			{
				pr[0]=make_pair(i,j);
			}
			else if(s[i][j]>='0'&&s[i][j]<='8')
			{
				pr[s[i][j]-'0']=make_pair(i,j);
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		c+=bfs(pr[i-1].first,pr[i-1].second,i);
	}
	cout<<c<<endl;
	return 0;
}

Measured memory_bytes: 7856
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> to(n);
  rep(i,m) {
    int s, t;
    cin >> s >> t;
    --s; --t;
    to[s].push_back(t);
  }
  vector<double> dp(n);
  // dp[n-1] = 0;
  for (int v = n-2; v >= 0; --v) {
    double now = 0;
    for (int u : to[v]) {
      now += dp[u];
    }
    now /= to[v].size();
    now += 1;
    dp[v] = now;
  }
  double ans = dp[0];
  for (int nv = 0; nv < n-1; nv++) {
    if (to[nv].size() == 1) continue;
    int nu = to[nv][0];
    for (int u : to[nv]) {
      if (dp[nu] < dp[u]) nu = u;
    }

    double now = [&]{
      vector<double> dp(n);
      for (int v = n-2; v >= 0; --v) {
        double now = 0;
        for (int u : to[v]) {
          if (v == nv && u == nu) continue;
          now += dp[u];
        }
        int deg = to[v].size();
        if (v == nv) deg--;
        now /= deg;
        now += 1;
        dp[v] = now;
      }
      return dp[0];
    }();
    ans = min(ans, now);
  }

  printf("%.10f\n", ans);
  return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define int long long
#define P pair<int,int>
using namespace std;
const int N = 1e7+7;
const int mod = 9901;
int a[N];

int cal(int a,int b){
    if(b%a == 0){
        return b/a*a*2-a;
    }
    else{
        return b/a*a*2+cal(b%a,a);
    }
}


signed main(){
    int n,x;
    cin>>n>>x;
    int s1 = x;
    int s2 = n-x;
    if(s2 == s1){
        cout<<s1*3<<endl;
    }else if(s2 > s1){
        cout<<s1+s2+cal(s1,s2)<<endl;
    }else{
        cout<<s1+s2+cal(s2,s1)<<endl;
    }
}


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

int main(void) {
	string s;
	cin >> s;
	int b = 0;
	long long b_sum = 0;
	long long sum = 0;

	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'B') {
			b_sum += i;
			b++;
		}
	}

	for (int i = s.size() - b; i < s.size(); i++) {
		sum += i;
	}

	cout << sum - b_sum <<  endl;
	return 0;
}


Measured memory_bytes: 640
#include <stdio.h>
#include <stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){


}

Node treeMaximum(Node x){


}

Node treeSearch(Node u, int k){


}

Node treeSuccessor(Node x){


}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y



}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x!=NIL)
    {
      y=x;
      if(z->key < x->key)
	{
	  x=x->left;
	}
      else
	{
	  x=x->right;
	}
    }
  z->parent=y;

  if(y==NIL)
    {
      root=z;
    }
  else if(z->key < y->key)
    {
      y->left=z;
    }
  else
    {
      y->right=z;
    }
  




}

void inorder(Node u){

  if(u==NIL) return;
  inorder(u->left);
  
  printf(" %d",u->key);
  inorder(u->right);
 
}
void preorder(Node u){
  
  if(u==NIL) return;
  
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}



Measured memory_bytes: 25176
#include<iostream>
#include<iomanip>
#include<string>
#include<queue>
#include<vector>
#include<algorithm>
#include<tuple>
#include<numeric>
#include<map>
#include<cmath>
#define ll long long
#define mod 1000000000+7
#define rep(i,n) for(int i=0;i<(int) (n);i++)
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
using namespace std;
int main() {
	int a, b,i=0;
	cin >> a >> b;
	a -= 1;
	bool bo=true;
	while (bo) {
		if (1 + a*i >= b)bo = false;
		else i++;
	}

	cout << i;
}

Measured memory_bytes: 256
from operator import itemgetter

N = int(input())
A = []

for _ in range(N):
    a, b = map(int, input().split())
    A.append((a - b, a + b))
A.sort(key=itemgetter(1))

res = 1
cur = A[0]

for i, a in enumerate(A):
    if i == 0:
        continue
    if a[0] >= cur[1]:
        res += 1
        cur = a

print(res)


Measured memory_bytes: 18284
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<functional>
#include<algorithm>
#include<cstdio>
#include<unordered_map>
using namespace std;
#define int long long
const int inf = 999999999999999999;
struct P {
	int pos, cost;
};
bool operator<(P a, P b) { return a.cost < b.cost; }
bool operator>(P a, P b) { return a.cost > b.cost; }
struct B {
	int to, cost;
};
typedef long long ll;
typedef long double ld;
signed main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	int ans = min(b, d) - max(a, c);
	cout << max(ans, 0LL) << endl;
	getchar(); getchar();
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#define M 100+5
int main(){
	char s[M],t[M],c,s1[M];
	scanf("%s%s",s,t);
	memset(s1,'\0',sizeof(s1));
	int l=strlen(s),i,j;
	for(j=1;j<=l;j++){
		c=s[l-1];
		for(i=l-1;i>0;i--){
			s[i]=s[i-1];
		}
		s[i]=c;
		if(strcmp(t,s)==0)break;
	//printf("%s\n",s);
	//for(i=0,j=l-1;i<l,j>=0;i++,j--){
		//s1[i]=s[j];
	//}
	//printf("%s\n",s1);
	}
	if(strcmp(t,s)==0)printf("Yes");
	else printf("No");
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF (1ll << 60)
#define sz(x) int(x.size())
using namespace std;
template <typename T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
typedef long long ll;
using vl = vector<ll>;
using vvl = vector<vl>;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
using ll = long long;
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;
}

void print(const std::vector<ll> &v) {
    std::for_each(v.begin(), v.end(), [](ll x) { std::cout << x << " "; });
    std::cout << std::endl;
}

double to_deg(double r) { return r * 180.0 / (atan(1.0) * 4.0); }

int main() {
    int N, T;
    cin >> N >> T;
    vector<int> A(N), B(N);
    vector<pair<int, int>> C(N);
    REP(i, N) {
        cin >> A[i] >> B[i];
        C[i] = make_pair(A[i], B[i]);
    }
    vector<vector<int>> dp(N + 1, vector<int>(T, 0));
    // T秒後に食べ終わるとしてiまで使ってよい
    // DPループ
    sort(C.begin(), C.end());
    for(int i = 0; i < N; ++i) {
        for(int w = 0; w <= T - 1; ++w) {
            if(w >= C[i].first)
                dp[i + 1][w] =
                    max(dp[i][w - C[i].first] + C[i].second, dp[i][w]);
            else
                dp[i + 1][w] = dp[i][w];
        }
    }
    int ans = 0;
    REP(i, N) { ans = max(ans, dp[i][T - 1] + C[i].second); }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 35584
#include <stdio.h>
int main(void){
    int i,j,m,H,W;
    m = 1;
    while(1){
        scanf("%d %d",&H,&W);
        if(H == 0 && W == 0)break;
        for(j = 0;j < H; j++){
            for(i = 0;i < W; i++){
                if(j == 0 || j == H-1 ||i == 0 || i == W-1){
            printf("#");
                }else{
                    printf(".");
                }
            }
            printf("\n");
        } 
        printf("\n");
    
    m++;
    }
    
    
  return 0;

 }


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

#define pi 3.141592654
#define fix(n) cout << fixed << setprecision(n)

#define rep(i,a,b) for(int i=a;i<b;i++)
#define ren(i,a,b) for(int i=a;i>=b;i--)

#define ll  long long
#define ull unsigned long long

#define mp make_pair
#define pb push_back
#define fi first
#define se second

#define vi      vector<int>
#define pii     pair<int,int>
#define piii    pair<pair<int,int>,int>
#define all(v)  v.begin(), v.end()

int mod = 1000000007;
const int N = 2005;
int div(int n)
{
	int cnt = 0;
	for (int i = 1; i * i <= n; i ++)
	{
		if ( n % i == 0)
		{
			cnt ++;
		
		if ( n / i != i)
			cnt++;
		}
	}
	return cnt;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 1; i <= n; i += 2)
	{
		if ( div(i) == 8)
			{
				//cout << i << " " << div(i) <<endl;
				ans ++;
			}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
<?php

fscanf(STDIN, "%d %s", $in_a, $in_b);
$b = explode(".", $in_b);
//var_dump($b);
$b[1] = substr($b[1]."00", 0, 2);
//var_dump($b);
$a = intdiv($in_a * (($b[0] * 100) + $b[1]) , 100);
$ans = (int)$a;

echo "$ans\n";


Measured memory_bytes: 16188
#include <stdio.h>

int main(void){
    int a, b, c, tmp;
    scanf("%d %d %d", &a, &b, &c);
    if (a > b){
        tmp = a;
        a = b;
        b = tmp;
    }
    if (b > c) {
        tmp = b;
        b = c;
        c = tmp;
    }
    if (a > b){
        tmp = a;
        a = b;
        b = tmp;
    }
    printf("%d %d %d\n", a, b, c);
    return 0;
}


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

using namespace std;

typedef long long int ll;
typedef pair<int,int> P;

#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<(b);i++)
#define repr(i,b,a) for(int i=int(b);i>=(a);i--)
#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool valid(int lx,int ux,int ly,int uy,int x,int y){
	return lx<=x&&x<ux&&ly<=y&&y<uy; 
}
ll power(ll x,ll p){
	if(p==0)return 1;
	ll res=power(x*x%mod,p/2);
	if(p%2==1)res=res*x%mod;
	return res;
}

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

	vector<vector<ll>> dp(n+1,vector<ll>(n+1,0));

	repi(len,1,n+1){
		repi(l,0,n-len+1){
			int r = l+len;
			if((n-len)%2==0){
				dp[l][r] = max(dp[l+1][r]+a[l], dp[l][r-1]+a[r-1]);
			}else{
				dp[l][r] = min(dp[l+1][r]-a[l], dp[l][r-1]-a[r-1]);
			}
		}
	}
	cout<<dp[0][n]<<endl;

	return 0;
}

Measured memory_bytes: 73696
#include <iostream>
using namespace std;
int main(void) {
	int na;
	int nb;
	int nc;
	int nd;
	int a=0;
	int b=0;
	int c=0;
	int d=0;
	cin >> na;
	cin >> nb;
	cin >> nc;
	cin >> nd;
	if ((na == 1) || (nb == 1) || (nc == 1) || (nd == 1))
		a = 1;
	if ((na == 9) || (nb == 9) || (nc == 9) || (nd == 9))
		b = 1;
	if ((na == 7) || (nb == 7) || (nc == 7) || (nd == 7))
		c = 1;
	if ((na == 4) || (nb == 4) || (nc == 4) || (nd == 4))
		d = 1;

	if ((a == 1) && (b == 1) && (c == 1) && (d == 1))
		cout << "YES";
	else
		cout << "NO";

	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

		InputStreamReader is = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(is);

		String str;
		while((str=br.readLine())!=null){
			String[] sp = str.split(",");
			int s =Integer.parseInt(sp[0]);
			double w =Double.parseDouble(sp[1]);
			double h =Double.parseDouble(sp[2]);

			if(w / (h * h) >= 25){
				System.out.println(s);
			}
		}
	}
}

Measured memory_bytes: 24196
#include<bits/stdc++.h>//本当は必要なヘッダファイルだけインクルードするべきです
using namespace std;//本当は個別にusingするか変数や関数ごとにstd::をつけるべきです
//本当は関数内に宣言し明示的に初期化するべきです
int n,b,t,ans=INT_MIN;
int main(void){
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>t;
    if(i==0)b=t;
    else{
      ans=max(ans,t-b);
      if(t<=b)b=t;
    }
  }
  cout<<ans<<endl;
  return 0;
}



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

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
tree<int,int,greater<int>,rb_tree_tag,tree_order_statistics_node_update> map_t;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for(int i = 0; i < (a); ++i)
#define sz(x) (int)x.size()
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define REV(x) reverse(x.begin(),x.end())
int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};

int main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    cin >> s;
    F0R(i,sz(s)) {
        if(s[i]=='?')
            cout << 'D';
        else
            cout << s[i];
    }

    return 0;
}


Measured memory_bytes: 3784
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Prime Number II
 */
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";

		int N = 50021;
		boolean[] prims = new boolean[N + 1];

		prims = new boolean[N + 1];
		for (int i = 2; i < N / 2 + 1; i++) {
			if (!prims[i]) {
				for (int j = 2; j < N / i + 1; j++) {
					prims[i * j] = true;
				}
			}
		}

		int primU = 0, primL = 0;
		while ((line = br.readLine()) != null && !line.isEmpty()) {
			int n = Integer.parseInt(line);
			//U
			for (int i = n + 1; ; i++) {
				if (!prims[i]) {
					primU = i;
					break;
				}
			}
			//L
			for (int i = n - 1; ; i--) {
				if (!prims[i]) {
					primL = i;
					break;
				}
			}
			System.out.println(primL + " " + primU);
		}
	}
}

Measured memory_bytes: 18944
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
    int n;
    cin >> n;
    vector<P> x(n);
    rep(i,n) {
        int xi;
        cin >> xi;
        x.at(i) = {xi, i};
    }
    sort(x.begin(), x.end());
    vector<int> ans(n);
    rep(i,n) {
        if (i < n/2) ans.at(x.at(i).second) = x.at(n/2).first;
        else ans.at(x.at(i).second) = x.at(n/2 - 1).first;
    }
    rep(i,n) cout << ans.at(i) << endl;
    return 0;
}

Measured memory_bytes: 5576
#include<iostream>
#include<set>

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, x, n) for (int i = x; i < (n); ++i)
using namespace std;

// using ll = long long;
// using P = pair<int, int>;

int main() {
    int N;
    int A[110];

    cin >> N;
    rep(i, N) cin >> A[i];

    set<int> st;
    rep(i, N) {
      st.insert(A[i]); // 値を追加．すでに格納されている場合無視される．
    }

    cout << st.size() << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
     
    using namespace std;
     
    const int N = 105, K = 1e5 + 5, MOD = 1e9 + 7;
    int n, p, dp[N][K], prefix[N][K], a[N];
     
    inline int add(int a, int b){
    	a += b;
    	if(a >= MOD)a -= MOD;
    	return a;
    }
     
    inline int sub(int a, int b){
    	a -= b;
    	if(a < 0)a += MOD;
    	return a;
    }
     
    int main(){
    	ios_base::sync_with_stdio(0);
    	cin.tie(0); cout.tie(0);
     
    	cin>>n>>p;
    	for(int i=1;i<=n;++i)cin>>a[i];
     
    	for(int i=0;i<=n;++i)dp[i][0] = prefix[i][0] = 1;
    	for(int j=0;j<=p;++j)prefix[0][j] = 1;
     
    	for(int i=1;i<=n;++i)
    		for(int j=1;j<=p;++j){
    			// coefficient of x^j is prefix[i - 1][j - a[i] : j];
     
    			int first = (j - a[i] - 1 >= 0)? prefix[i - 1][j - a[i] - 1] : 0;
    			int last = prefix[i - 1][j];
    			dp[i][j] = add(dp[i][j], sub(last, first));
    			prefix[i][j] = add(prefix[i][j - 1], dp[i][j]);
    		}
     
    	cout<<dp[n][p]<<"\n";
    	return 0;
    }

Measured memory_bytes: 82176
import numpy as np

w, h, n = map(int, input().split())
area = np.zeros((w, h))

for i in range(n):
    x, y, a = map(int, input().split())
    if a==1:
        area[:x, :] = 1
    elif a==2:
        area[x:, :] = 1
    elif a==3:
        area[:, :y] = 1
    else:
        area[:, y:] = 1

print((w*h) - int(area.sum()))


Measured memory_bytes: 27284
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;cin>>n;
  int a,b,c;
  a=n%10;
  n=n/10;
  b=n%10;
  n=n/10;
  c=n%10;
  if(a==7||b==7||c==7)
    cout<<"Yes";
  else
    cout<<"No";
  return 0;
}

Measured memory_bytes: 3592
import java.io.*;
import java.util.*;

public class Main{
	public static void main(String args[]){
		try{
			new Main();
		}catch(IOException e){
			e.printStackTrace();
		}
	}

	public Main() throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String line;

		while((line = in.readLine()) != null){
			int n = Integer.parseInt(line);
			if(n==0) break;
			int size = n/2;
			List<Integer> data = new ArrayList<Integer>();
			for(int i=1; i<=size; i++){
				int m = (i * i) % n;
				if(!data.contains(m)){
					data.add(m);
				}
			}

			int s = data.size();
			int[] result = new int[size];

			for(int i=0; i<s; i++){
				for(int j=0; j<s; j++){
					if(i!=j){
						int m = data.get(i) - data.get(j);
						if(m < 0) m += n;
						if(m > size) m = n - m;
						result[m-1]++;
					}
				}
			}

			for(int i=0; i<size; i++){
				System.out.println(result[i]);

			}
		}


	}
}

Measured memory_bytes: 10000
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())



bool kaibun(string s) {
	int n = s.size();
	for (int i = 0; i < s.size();i++) {
		if (s[i] != s[n-1-i]) {
			return false;
		}
	}

	return true;
}

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

	string s;
	cin >> s;
	int n = s.size();
	cout << (kaibun(s) && kaibun(s.substr(0, (n-1)/2)) && kaibun(s.substr((n + 3) / 2 - 1)) ? "Yes" : "No") << endl;



	return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFIMES
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

const int MOD = 1'000'000'007;
const int INF = 1'000'000'000; //1e9
const int NIL = -1;
const long long LINF = 1'000'000'000'000'000'000; // 1e18
const long double EPS = 1E-10;

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








int main(){
    int K; std::cin >> K;
    int a(0);
    for(int i(1); i <= K+3; ++i){
        a = (10 * a + 7) % K;
        if(!a){
            std::cout << i << std::endl;
            return 0;
        }
    }
    std::cout << -1 << std::endl;
    return 0;
}


Measured memory_bytes: 3632
#include<iostream>

using namespace std;

int main(){
  int n,i;
  
  //cout<< "宝石の個数を入力（１以上２０以下の整数）" <<endl;
  cin >> n;
  //cout<< "宝石の価値を入力（１以上５０以下の整数）" <<endl;
  int v[n];
  for(i=0;i<n;i++){
    cin >> v[i];
  }
  //cout<< "宝石のコストを入力（１以上５０以下の整数）" <<endl;
  int c[n];
  for(i=0;i<n;i++){
    cin >> c[i];
  }
  
 int a=0;
  for(i=0;i<n;i++){
    if(v[i]>c[i]){
    	a+=v[i]-c[i];
    }
  }
  cout << a << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <tuple>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <cassert>

using namespace std;
using ll = long long;

int main()
{
    int n, k, x, y;
    cin >> n >> k >> x >> y;
    int ans = 0;
    if(n > k){
        ans += x * k;
        ans += (n-k)*y;
    }else{
        ans += x*n;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3552
n, m = map(int, input().split())
x = list(map(int, input().split()))

if n >=m:
    print(0)
    exit(0)

x.sort()

d = [x[i+1] - x[i] for i in range(m-1)]
d.sort()

print(sum(d[0:m-n]))


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

int main(){
	vector<pair<char,int>> vp;
	string s;
	cin>>s;
	int ss=s.size(),vs=-1,ans=0;
	pair<char,int> p;
	p.first='A'; p.second=1;
	for(int i=0;i<ss;i++){
		if(s[i]==p.first)vp[vs].second++;
		else {
			p.first=s[i];
			vp.push_back(p);
			vs++;
		}
	}
	for(int i=0;i<=vs-2;i++){
		if(vp[i].first=='J'&&vp[i+1].first=='O'&&vp[i+2].first=='I'&&min(vp[i].second,min(vp[i+1].second,vp[i+2].second))==vp[i+1].second){
			if(vp[i+1].second>ans)ans=vp[i+1].second;
		}
	}
	printf("%d\n",ans);
}

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

using namespace std;

int main(){
  int A_h = 0;  int A_m = 0;  int A_s = 0;
  int A2_h = 0;  int A2_m = 0;  int A2_s = 0;
  int A3_h = 0;  int A3_m = 0;  int A3_s = 0;
  int B_h = 0;  int B_m = 0;  int B_s = 0;
  int B2_h = 0;  int B2_m = 0;  int B2_s = 0;
  int B3_h = 0;  int B3_m = 0;  int B3_s = 0;
  int C_h = 0;  int C_m = 0;  int C_s = 0;
  int C2_h = 0;  int C2_m = 0;  int C2_s = 0;
  int C3_h = 0;  int C3_m = 0;  int C3_s = 0;

  cin>>A_h;  cin>>A_m;  cin>>A_s;
  cin>>A2_h;  cin>>A2_m; cin>>A2_s;

  cin>>B_h;  cin>>B_m;  cin>>B_s;
  cin>>B2_h;  cin>>B2_m;  cin>>B2_s;

  cin>>C_h;  cin>>C_m;  cin>>C_s;
  cin>>C2_h;  cin>>C2_m;  cin>>C2_s;


  if(A2_s < A_s){
    A2_s += 60;  A2_m -= 1;  A3_s = A2_s - A_s;
  }
  else{
    A3_s = A2_s - A_s;
  }
  if(A2_m < A_m){
    A2_m += 60;  A2_h -= 1;  A3_m = A2_m - A_m;
  }
  else{
    A3_m = A2_m - A_m;
  }
  A3_h = A2_h - A_h;


  if(B2_s < B_s){
    B2_s += 60;  B2_m -= 1;  B3_s = B2_s - B_s;
  }
  else{
    B3_s = B2_s - B_s;
  }
  if(B2_m < B_m){
    B2_m += 60;  B2_h -= 1;  B3_m = B2_m - B_m;
  }
  else{
    B3_m = B2_m - B_m;
  }
  B3_h = B2_h - B_h;


  if(C2_s < C_s){
    C2_s += 60;  C2_m -= 1;  C3_s = C2_s - C_s;
  }
  else{
    C3_s = C2_s - C_s;
  }
  if(C2_m < C_m){
    C2_m += 60;  C2_h -= 1;  C3_m = C2_m - C_m;
  }
  else{
    C3_m = C2_m - C_m;
  }
  C3_h = C2_h - C_h;

  cout<<A3_h<<" "<<A3_m<<" "<<A3_s<<endl;
  cout<<B3_h<<" "<<B3_m<<" "<<B3_s<<endl;
  cout<<C3_h<<" "<<C3_m<<" "<<C3_s<<endl;

  return 0;
}


Measured memory_bytes: 3048
def poor(A,B,C):
  if (A==B and A!=C) or (B==C and A!=B) or (A==C and A!=B):
    print('Yes')
  else:
    print('No')
a = input()
# => "a b c"
a=a.split()
# => ["a","b","c"]
b=[]
for i in  a:
  b.append(int(i))
# => b=[a,b,c]

poor(b[0],b[1],b[2])

Measured memory_bytes: 3060
import fractions

A, B, C, D = [int(i) for i in input().split()]
A = A - 1
l = (C * D) // fractions.gcd(C,D)

b_sum = B -(B//C) - (B//D) + (B//l)
a_sum = A - (A//C) - (A//D) + (A//l)

print(b_sum - a_sum)    


Measured memory_bytes: 5048
def rs(X, Y, i):
  if i not in Y:
    return 0
  elif len(Y)==1:
    return 1
  Y.remove(i)
  
  total=0
  X_tmp=[x for x in X if x[0]==i or x[1]==i]
  for x in X_tmp:
    if x[0]==i and x[1] in Y:
      target=x[1]
    elif x[1]==i and x[0] in Y:
      target=x[0]
    else:
      continue
    total+=rs(X, Y[:], target)
    
  return total
  

N,M=map(int, input().split())
X=[list(map(int,input().split())) for _ in range(M)]
Y=[i+1 for i in range(N)]
print(rs(X, Y, 1))

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

using namespace std ;

const int N=1e5+100 ;

char s[N] ;
int n ;

int main ()
{
	int i , ans , res ;
	scanf("%s",s+1),n=strlen(s+1);
	ans=0 ;
	for ( i=1 ; i<=n ; i++ ) ans+=(s[i]!=((i&1)+'0'));
	res=ans,ans=0;
	for ( i=1 ; i<=n ; i++ ) ans+=(s[i]!=((~i&1)+'0'));
	res=min(res,ans);
	printf("%d\n",res);
	return 0 ;
}

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

using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif

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


    lint n, m;
    cin >> n >> m;

    lint ans=0;

    vector<lint> h(n),v(n);
    REP(i, n) { cin >> h[i]; }

    REP(i, m){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        if(h[a]>=h[b])
            v[b] = 1;
        if (h[b] >= h[a])
            v[a] = 1;
    }
    REP(i,n){
        ans += 1 - v[i];
    }
    
    cout << ans <<"\n";

    return 0;
}

Measured memory_bytes: 4768
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

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

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))


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

    int n;
    cin >> n;

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

    sort(a.begin(), a.end());
    sort(c.begin(), c.end());

    s64 ans = 0;
    rep (i, n)
    {
        s64 l = lower_bound(a.begin(), a.end(), b[i]) - a.begin();
        s64 r = c.end() - upper_bound(c.begin(), c.end(), b[i]);
        ans += l * r;
    }

    cout << ans << "\n";
    return 0;
}



Measured memory_bytes: 1408
N, M = map(int, input().split())
a, b = [], []
for _ in range(N):
    A, B = map(int, input().split())
    a.append(A)
    b.append(B)
    
c, d = [], []
for _ in range(M):
    C, D = map(int, input().split())
    c.append(C)
    d.append(D)
    
for A, B in zip(a, b):
    ans = 0
    mn = 10**9
    for i, (C, D) in enumerate(zip(c, d)):
        s = abs(A - C) + abs(B - D)
        if mn > s:
            ans = i
            mn = s
            
    print(ans+1)

Measured memory_bytes: 3064
/*
Author: Babin Dutta
*/

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define pb push_back
#define mp make_pair
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define f(i,n) for(int i=0;i<n;i++)
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define all(v) v.begin(),v.end()
#define endl "\n"
#define inf 1e18

void solve(int tt){
	ll k; cin>>k;
	ll a,b; cin>>a>>b;
	ll x = a/k;
	ll y = b/k;
	if(x != y){
		cout<<"OK"<<endl;
		return;
	}
	else if(a%k == 0 || b%k == 0) cout<<"OK"<<endl;
	else cout<<"NG"<<endl;
}

int main(){
	#ifdef JUDGE
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    #endif
	boost;
	int t=1; //cin>>t;
	for(int i=1;i<=t;i++) solve(i);
	return 0;
}

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

#define rep(i,n) for(int i=0; i<(n); ++i)
using ll = long long;
using P = pair<int, int>;
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;}

const int MAX_N = 1e3+3;
const int MAX_W = 1e5+3;
ll dp[MAX_N][MAX_W];

int main() {
  int n, w;
  cin >> n >> w;
  vector<P> v(n);
  rep(i,n) cin >> v[i].first >> v[i].second;

  rep(i,n) {
    for (int j=0; j<=w; ++j) {
      if (j - v[i].first >= 0) chmax(dp[i+1][j], dp[i][j-v[i].first] + v[i].second);
      chmax(dp[i+1][j], dp[i][j]);
    }
  }

  cout << dp[n][w] << endl;
  return 0;
}


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

using namespace std;
int n, m, q, a[59], b[59], c[59], d[59];
int A[19];
int mx=0;

void check(){
  int cnt = 0;
  for(int i=0;i<q;i++){
    if(A[b[i]] - A[a[i]] == c[i])cnt+=d[i];
  }
  mx = max(mx, cnt);
}

void recursive_search(int idx){
  if(idx==n)check();
  else{
    for(int i=A[idx-1];i<=m;i++){
      A[idx] = i;
      recursive_search(idx+1);
    }
  }
}

int main(){
  cin >> n >> m >> q;
  for(int i=0;i<q;i++){
    cin >> a[i] >> b[i] >> c[i] >> d[i];
    a[i]--;
    b[i]--;
  }
  for(int i=1;i<=m;i++){
    A[0] = i;
    recursive_search(1);
  }
  cout << mx << endl;
}



Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
  if(b==0){
    return a;
  }
  return gcd(b,a%b);
}
int main(){
  int n,X;
  cin >> n >> X;
  vector<int> x(n);
  for(int i=0;i<n;i++){
    cin >> x[i];
  }
  int r;
  if(n==1){
    r=abs(x[0]-X);
  }
  if(n>=2){
    r=gcd(abs(X-x[0]),abs(X-x[1]));
    for(int i=1;i<n-1;i++){
      r=min(r,gcd(abs(X-x[i]),abs(X-x[i+1])));
    }
  }
  cout << r << endl;
}

Measured memory_bytes: 640
use std::collections::BTreeMap;
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let n: usize = read();
    let m: u64 = read();
    let a: Vec<u64> = (0..n).map(|_| read()).collect();

    let mut b = vec![0; n + 1];

    for i in 0..n {
        b[i + 1] = b[i] + a[i];
    }
    for b_i in b.iter_mut() {
        *b_i %= m;
    }
    let mut map = BTreeMap::new();
    for b in b {
        *map.entry(b).or_insert(0) += 1;
    }
    let ans: u64 = map.iter().map(|(&_, &v)| (v * (v - 1)) / 2).sum();

    println!("{}", ans);
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


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

#define rep(i,n) for(int i=0; i<n; i++)
#define rept(i,a,b) for(int i=a; i<b; i++)
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef vector<int> vi;

int main() {
	int x, a, b;
	cin >> x >> a >> b;

	if(abs(x - a) < abs(x - b)){
		cout << "A" << endl;
	}else{
		cout << "B" << endl;
	}



    return 0;
}



Measured memory_bytes: 256
function Main(input) {
    var result;
    const P = parseInt(input[0])
    const Q = parseInt(input[1])
    const R = parseInt(input[2])
    console.log(Math.min(P+Q, Q+R, R+P));
}

// 1行入力の場合
// Main(require("fs").readFileSync("/dev/stdin", "utf8").trim());

// 改行で分割
// Main(require("fs").readFileSync("/dev/stdin", "utf8").trim().split(/\n/));

// 改行・空白で分割
Main(require("fs").readFileSync("/dev/stdin", "utf8").trim().split(/\n|\s/));

Measured memory_bytes: 21064
import sys

input=sys.stdin.readline

N,K=map(int,input().split())
integer=[]
for i in range(N):
    a,b=map(int,input().split())
    integer.append([a,b])

bit=[]
for i in range(0,30):
    if K>>i &1==1:
        bit.append(i)

ans=0
for j in range(N):
    a,b=integer[j]
    if a|K==K:
        ans+=b

for i in bit:
    check=(K>>i)-1
    test=0
    for j in range(N):
        a,b=integer[j]
        if a>>i|check==check:
            test+=b
    ans=max(ans,test)

print(ans)


Measured memory_bytes: 54748
#include <iostream>
#include <vector>

int main(){
  long long N;
  std::cin >> N;


  long long resa = 0;
  for(int i = 1 ; i <= N ; i++){
    if(i % 3 != 0 && i % 5 != 0){
      resa += i;
    }
  }
  std::cout << resa << std::endl;
  return 0;
 
}


Measured memory_bytes: 3624
N, M = map(int, input().split())
S = input()
T = input()
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)
def lcm(a, b):
    return a * b // gcd(a, b)
l = lcm(N, M) 
print(lcm(N, M)) if all(S[(l//M) * i] == T[(l//N) * i] for i in range(gcd(N, M))) else print(-1)

Measured memory_bytes: 3316
n,k = map(int,input().split())
mod = 1000000007
cnt = [0]*(k+1)
for i in range(1,k+1)[::-1]:
    cnt[i] = pow(k//i,n,mod)
    for j in range(2*i,k+1,i):
        cnt[i] -= cnt[j]
        cnt[i] %= mod
ans = 0
for i in range(1,k+1):
    ans += cnt[i]*i
    ans %= mod
print(ans)

Measured memory_bytes: 11256
#include <stdio.h>
#include <string.h>

int main() {
	int n, AC = 0, WA = 0, TLE = 0, RE = 0;
	char wha[5];
	scanf ("%d", &n);
	
	for (int i = 1; i <= n; i++) {
		scanf ("%s", &wha);
		if (strcmp(wha, "AC") == 0) {
			AC += 1;
			continue;
		}
		else if (strcmp(wha, "WA") == 0) {
			WA += 1;
			continue;
		}
		else if (strcmp(wha, "TLE") == 0) {
			TLE += 1;
			continue;
		}
		else if (strcmp(wha, "RE") == 0) {
			RE += 1;
			continue;
		}
	}
	printf ("AC x %d\n", AC);
	printf ("WA x %d\n", WA);
	printf ("TLE x %d\n", TLE);
	printf ("RE x %d\n", RE);
	
	return 0;
}

Measured memory_bytes: 1732
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cassert>
using namespace std;

#define REP(i,n) for (int i = 0; i < n; i++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long ll;

int main ()
{
    ll N,M;
    cin >> N >> M;
    vector < ll > x[3];
    REP(i,N) {
        ll a,b,c;
        cin >> a >> b >> c;
        x[0].push_back(a);
        x[1].push_back(b);
        x[2].push_back(c);
    }

    ll ans = 0;
    REP(i, 1 << 3) {
        vector < vector < ll > > ord = vector < vector < ll > >(N, vector < ll > (3));
        REP(j,3) {
            if ((i >> j) & 1) {
                REP(k,N) {
                    ord[k][j] = x[j][k];
                }
            } else {
                REP(k,N) {
                    ord[k][j] = -x[j][k];
                }
            }
        }
        vector < ll > sum;
        REP(i,N) {
            sum.push_back(ord[i][0] + ord[i][1] + ord[i][2]);
        }
        sort(sum.begin(), sum.end());
        reverse(sum.begin(), sum.end());
        ll anst = 0;
        REP(i,M) {
            anst += sum[i];
        }
        ans = max(ans, anst);
    }

    cout << ans << endl;

    return 0;
}


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

int A,B,C;

int main()
{
    scanf("%d%d%d",&A,&B,&C);
    int sum = A;
    for(int i = 0; i < B; i++)
    {
        if(sum % B == C)
        {
            printf("YES\n");
            return 0;
        }
        sum += A;
    }
    printf("NO\n");
    return 0;
}


Measured memory_bytes: 256
N = int(input())
li = []
li = list(map(int, input().split()))

flag = True
for i in range(0, N):
  if i + 1 != li[i]:
    if flag == False:
      print("NO")
      break
    for j in range(i + 1, N):
      if li[j] == i + 1:
        li[i] = i + 1
        li[j] = j + 1
        flag = False
else:
  print("YES")


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

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

  if (x < 1200) {
    cout << "ABC" << endl;
  }
  else if (x < 2800) {
    cout << "ARC" << endl;
  }
  else if(x <= 4208){
    cout << "AGC" << endl;
  }
}


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

#define dump(...) do{print_vars(cout<<"# "<<#__VA_ARGS__<<'=',__VA_ARGS__);cout<<endl;}while(0)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vd=vector<double>;
using vvd=vector<vd>;
using vs=vector<string>;

void print_vars(ostream&){}
template<typename Car,typename... Cdr>
void print_vars(ostream& os,const Car& car,const Cdr&... cdr){
	print_vars(os<<car<<(sizeof...(cdr)?",":""),cdr...);
}

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}

template<int I,typename Tuple>
void print_tuple(ostream&,const Tuple&){}
template<int I,typename Car,typename... Cdr,typename Tuple>
void print_tuple(ostream& os,const Tuple& t){
	os<<get<I>(t)<<(sizeof...(Cdr)?",":"");
	print_tuple<I+1,Cdr...>(os,t);
}
template<typename... Args>
ostream& operator<<(ostream& os,const tuple<Args...>& t){
	print_tuple<0,Args...>(os<<'(',t);
	return os<<')';
}

template<typename Ch,typename Tr,typename C>
basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){
	os<<'[';
	for(auto i=begin(c);i!=end(c);++i)
		os<<(i==begin(c)?"":" ")<<*i;
	return os<<']';
}

constexpr int INF=1e9;
constexpr int MOD=998244353;
constexpr double EPS=1e-9;

vi mod(vi a,vi b)
{
	int m=a.size(),n=b.size();
	int j=find(all(b),1)-begin(b);
	for(int i=0;i+(n-j)<=m;i++) if(a[i])
		rep(k,n-j) a[i+k]^=b[j+k];
	return a;
}

vi gcd(vi a,vi b)
{
	while(count(all(b),1))
		tie(a,b)=mt(b,mod(a,b));
	return vi(find(all(a),1),end(a));
}

int main()
{
	#ifndef _GLIBCXX_DEBUG
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	constexpr char endl='\n';
	#endif

	for(int n;cin>>n&&n;){
		vi x;
		{
			string s; cin>>s;
			rep(j,s.size()) x.push_back(s[j]-'0');
		}
		vvi a(n);
		rep(i,n){
			string s; cin>>s;
			rep(j,s.size()) a[i].push_back(s[j]-'0');
		}

		vi g=a[0];
		repi(i,1,n) g=gcd(g,a[i]);

		ll res=0;
		vi y(x.size());
		for(int i=0;i+g.size()<=y.size();i++){
			res=(res*2+x[i])%MOD;
			if(y[i]!=x[i])
				rep(j,g.size()) y[i+j]^=g[j];
		}
		if(x<y)
			res=(res-1+MOD)%MOD;
		cout<<res+1<<endl;
	}
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b) - 1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)

#define PB push_back
#define INF (1<<29)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define CLR(a) memset(a,0,sizeof(a))
const int dx[] = {-1,0,0,1},dy[] = {0,1,-1,0};

typedef long long int ll;

using namespace std;

int main(){
    int n;
    cin >> n;
    int c = n*(n-1)/2;
    int m = 0;
    vector<int> v(n,0);
    REP(i,c){
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	a--;
	b--;
	if(c > d) v[a] += 3;
	else if(d > c) v[b] += 3;
	else{
	    v[a]++;
	    v[b]++;
	}
	m = max(m,v[a]);
	m = max(m,v[b]);
    }
    vector<int> ans(n);
    int rank = 1;
    while(m >= 0){
	bool flg = false;
	int count = 0;
	REP(i,n){
	    if(v[i] == m){
		ans[i] = rank;
		flg = true;
		count++;
	    }
	}
	if(flg){
	    rank += count;
	}
	m--;
    }
    REP(i,n) cout << ans[i] << endl;
    return 0;
}

Measured memory_bytes: 1196
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>
#include <queue>
#include <sstream>
using namespace std;

const int MAX_V = 108;
const int H = 106;
const int D = 107;

int m, n, k, d, calorie[6];

struct Edge { int to, cost, cakeFlag; };
vector<Edge> G[MAX_V];

int dist[64][108];

int toInt(string s) {
	stringstream ss(s);
	int ret = 0;
	ss >> ret;
	return ret;
}

int makeKey(string s) {
	if (s[0] == 'C') return toInt(s.substr(1)) - 1;
	if (s[0] == 'L') return toInt(s.substr(1)) + 5;
	if (s == "H") return H;
	return D;
}

void addEdge(string a, string b, int cost) {
	int ak = makeKey(a);
	int bk = makeKey(b);
	if (b[0] == 'C') {
		G[ak].push_back((Edge){bk, cost - calorie[bk], 1 << bk});
	} else {
		G[ak].push_back((Edge){bk, cost, 0});
	}
	if (a[0] == 'C') {
		G[bk].push_back((Edge){ak, cost - calorie[ak], 1 << ak});
	} else {
		G[bk].push_back((Edge){ak, cost, 0});
	}
}

int shortestPath(int from, int to) {
	for (int i=0; i<64; ++i) {
		for (int j=0; j<108; ++j) {
			dist[i][j] = INT_MAX;
		}
	}
	dist[0][from] = 0;
	queue<pair<int,int> > q;
	q.push(make_pair(from, 0));
	while ( ! q.empty()) {
		int now = q.front().first;
		int flag = q.front().second;
		q.pop();
		for (int i=0; i<(int)G[now].size(); ++i) {
			Edge &e = G[now][i];
			if (flag & e.cakeFlag) continue;
			if (dist[flag][now] + e.cost < dist[flag | e.cakeFlag][e.to]) {
				dist[flag | e.cakeFlag][e.to] = dist[flag][now] + e.cost;
				q.push(make_pair(e.to, flag | e.cakeFlag));
			}
		}
	}
	int ret = INT_MAX;
	for (int i=0; i<64; ++i) {
		ret = min(ret, dist[i][to]);
	}
	return ret;
}

int main() {
	while (cin >> m >> n >> k >> d, m) {
		fill(G, G+MAX_V, vector<Edge>());
		for (int i=0; i<m; ++i) {
			cin >> calorie[i];
		}
		string a, b;
		int cost;
		for (int i=0; i<d; ++i) {
			cin >> a >> b >> cost;
			addEdge(a, b, cost * k);
		}
		cout << shortestPath(H, D) << endl;
	}
	return 0;
}

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

int main() {
  long n,ans=0;
  string s;
  cin >> n >> s;
  for(long i=1;i<n;i++) {
    long a=0;
    for(long j=0;i+j<n;j++) {
      if(i==a) a--;
      if(s[j]==s[i+j]) a++;
      else a=0;
      ans=max(ans,a);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 384
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try {
			//solve(new Scanner(new File("src\\h\\10-maximum00.in")));
			solve(new Scanner(System.in));
		} catch (Exception e) {
			e.printStackTrace();
		}

	}
	public static void solve(Scanner sc) {
		int n = sc.nextInt();
		int[] x = new int[n];
		for(int i=0;i<n;i++) {
			x[i] = sc.nextInt();
		}
		RMQ dp = new RMQ(n+1);
		for(int i=0;i<n;i++) {
			long max = x[i];
			max = Math.max(max,max+dp.query(0,x[i]));
			dp.update(x[i], max);
			//System.out.println(dp);
		}
		long ans = n*(n+1L)/2;
		ans-=dp.query(0, n+1);
		System.out.println(ans);
		sc.close();
	}
}
class RMQ {
	private int size;
	private int size_ = 1;
	private long[] data;
	public RMQ(int size) {
		this.size = size;
		while(this.size_<this.size) {
			this.size_*=2;
		}
		data = new long[size_*2-1];
		this.init();
	}

	private void init() {
		Arrays.fill(data, -1);
	}

	public void update(int k,long a) {
		k+=size_-1;
		data[k] = a;
		while(k>0) {
			k=(k-1)/2;
			data[k] = Math.max(data[k*2+1],data[k*2+2]);
		}
	}

	public long query(int a,int b) {
		return query(a,b,0,0,size_);
	}

	//[a,b)の区間について処理
	//kは接点の番号,[l,r)がkに対応する節点
	public long query(int a,int b,int k,int l,int r) {
		if (r<=a || b<=l) {
			return Integer.MIN_VALUE;
		}
		if (a<=l && r<=b) {
			return data[k];
		}else{
			return Math.max(query(a,b,k*2+1,l,(l+r)/2)
					,query(a,b,k*2+2,(l+r)/2,r));
		}
	}

	public String toString() {
		String s = "";
		for(int i=0;i<size;i++) {
			s += query(i,i+1) + ",";
		}
		return s;
	}
}

Measured memory_bytes: 63752