Submission #1307163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307163		jahongir	Nice sequence (IZhO18_sequence)	C++20	76 / 100	2097 ms	54020 KiB

sequence

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

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

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef unsigned long long ull;
typedef vector<int> vi;


static const int buf_size = 4096;
 
inline int getChar() {
	static char buf[buf_size];
	static int len = 0, pos = 0;
	if (pos == len)
		pos = 0, len = fread(buf, 1, buf_size, stdin);
	if (pos == len)
		return -1;
	return buf[pos++];
}
 
inline int readChar() {
	int c = getChar();
	while (c <= 32)
		c = getChar();
	return c;
}
 
template <class T = int>
inline T readInt() {
	int s = 1, c = readChar();
	T x = 0;
	if (c == '-')
		s = -1, c = getChar();
	while ('0' <= c && c <= '9')
		x = x * 10 + c - '0', c = getChar();
	return s == 1 ? x : -x;
}
 
/** Write */
 
static int write_pos = 0;
static char write_buf[buf_size];
 
inline void writeChar( int x ) {
	if (write_pos == buf_size)
		fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
	write_buf[write_pos++] = x;
}
 
inline void flush() {
	if (write_pos)
		fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
}
 
template <class T = int> 
inline void writeInt( T x ) {
	if (x < 0)
		writeChar('-'), x = -x;
 
	char s[24];
	int n = 0;
	while (x || !n)
		s[n++] = '0' + x % 10, x /= 10;
	while (n--)
		writeChar(s[n]);
}


const int mxn = 1e6;
vector<int> g[mxn];
int indeg[mxn], pref[mxn];


void solve(){
    int n = readInt();
    int m = readInt();

    int l = 0, r = mxn;

    while(l+1 < r){
        int mid = (l+r)>>1;

        indeg[0] = 0;
        g[0].clear();
        for(int i = 1; i <= mid; i++){
            indeg[i] = 0;
            g[i].clear();
            if(i >= m){
                g[i].push_back(i-m);
                indeg[i-m]++;
            }
            if(i >= n){
                g[i-n].push_back(i);
                indeg[i]++;
            }
        }

        queue<int> qu;
        int cnt = 0;
        for(int i = 0; i <= mid; i++) if(indeg[i]==0)
            qu.push(i);
            
        while(!qu.empty()){
            auto u = qu.front(); qu.pop();
            cnt++;

            for(auto v : g[u])
                if(--indeg[v]==0)
                    qu.push(v);
        }

        if(cnt < mid) r = mid;
        else l = mid;
    }

    indeg[0] = 0;
    g[0].clear();
    for(int i = 1; i <= l; i++){
        indeg[i] = 0;
        g[i].clear();
        if(i >= m){
            g[i].push_back(i-m);
            indeg[i-m]++;
        }
        if(i >= n){
            g[i-n].push_back(i);
            indeg[i]++;
        }
    }

    queue<int> qu;
    int cnt = l;
    for(int i = 0; i <= l; i++) if(indeg[i]==0)
        qu.push(i);

    while(!qu.empty()){
        auto u = qu.front(); qu.pop();
        pref[u] = cnt--;
        for(auto v : g[u]) if(--indeg[v]==0)
            qu.push(v);
    }



    writeInt(l);
    writeChar('\n');
    for(int i = 1; i <= l; i++){
        writeInt(pref[i]-pref[i-1]);
        writeChar(' ');
    }
    writeChar('\n');
}   


signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int t = readInt();
    while(t--){solve();}
    flush();
}

• 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: 0 / 24