Submission #40367

#	Time	Username	Problem	Language	Result	Execution time	Memory
40367		model_code	Nice sequence (IZhO18_sequence)	C++11	100 / 100	733 ms	39572 KiB

sequence

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
#include <map>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <bitset>
#define f first
#define s second
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define pb push_back
#define vi vector <int>
#define ld long double
#define pii pair<int, int>
#define y1 sda
using namespace std;    
const int N = int(2e6) + 10, mod = int(1e9)  + 7; 

ll a[N], pref[N];
int pr[N], rnk[N], px[N], py[N], c[N];

int get(int v){
	if(pr[v] == v) return v;
	return pr[v] = get(pr[v]);
}

void Merge(int u,int v){
	u = get(u);
	v = get(v);
	if(u == v) return;
	if(rnk[u] > rnk[v]){
		pr[v] = u;
		rnk[u] += rnk[v];
	}
	else{
		pr[u] = v;
		rnk[v] += rnk[u];
	}
}

bool solve(int n,int m){
    bool sw = 0;
    if(n > m) {sw = 1, swap(n,m);}
    int ans = n + m - 1 - __gcd(n,m);
    if(m % n == 0){
        for(int i = 1; i < m; i++){
        	a[i] = -1;
        }
    }
    else{
    	ll ax = 0, bx = 0, ay = 0, by = 0;
    	for(int i = 1; i <= ans; i++){
    		pr[i] = i;
    		rnk[i] = 1;
    	}
    	for(int i = 1; i <= ans; i++){
    		if(i + n <= ans) Merge(i,i + n);
    		if(i + m <= ans) Merge(i,i + m);
    	}
    	int p1 = -1, p2 = -1;
    	int cn = 0;
    	for(int i = 1; i <= ans; i++){
    		get(i);
    		px[i] = py[i] = 0;
    		c[++cn] =  pr[i];
    	}
    	sort(c + 1, c + cn + 1);
    	cn = unique(c + 1, c + cn + 1) - c - 1;
    	for(int i = 1; i <= n; i++){
    		px[pr[i]]++;
    	}
    	for(int i = 1; i <= m; i++){
    		py[pr[i]]++;
    	}
    	ax = px[c[1]], ay = py[c[1]];
    	p1 = c[1];
    	for(int i = 2; i <= cn; i++){
    		if(1ll * ax * py[c[i]] > 1ll * ay * px[c[i]]){
    			ax = px[c[i]];
    			ay = py[c[i]];
    			p1 = c[i];
    		}
    	}
    	bx = n - ax;
    	by = m - ay;
    	ll vx = bx + by;
    	ll vy = -(ax + ay);
    	for(int i = 1; i <= ans; i++){
    		if(pr[i] == p1) a[i] = vx;
    		else a[i] = vy;
    	}

    }
    if(sw){
    	swap(n,m);
    	for(int i = 1; i <= ans; i++){
    		a[i] = -a[i];
    	}
    }
    printf("%d\n", ans);
    for(int i = 1; i <= ans; i++){
    	printf("%d", a[i]);
    	if(i < ans) printf(" ");
    }
    printf("\n");
}

int main () {
	int T,n,m;
	scanf("%d", &T);
	while(T--){
	    scanf("%d%d", &n, &m);
	    solve(n,m);
	}

return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'bool solve(int, int)':
sequence.cpp:70:19: warning: unused variable 'p2' [-Wunused-variable]
      int p1 = -1, p2 = -1;
                   ^
sequence.cpp:112:23: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
      printf("%d", a[i]);
                       ^
sequence.cpp:116:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
sequence.cpp: In function 'int main()':
sequence.cpp:120:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &T);
                 ^
sequence.cpp:122:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d%d", &n, &m);
                           ^

• Subtask 1: 6 / 6
• Subtask 2: 9 / 9
• Subtask 3: 14 / 14
• Subtask 4: 15 / 15
• Subtask 5: 14 / 14
• Subtask 6: 18 / 18
• Subtask 7: 24 / 24