https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Euler's_sieve

You can solve Problem D in O(n+A).

int n;

int p[10000005], ptop;
int pk[10000005];

void sieve() {
    int n = 10000000;
    for(int i = 2; i <= n; ++i) {
        if(!pk[i]) {
            p[++ptop] = i;
            pk[i] = i;
        }
        for(int j = 1; j <= ptop; ++j) {
            int t = i * p[j];
            if(t > n)
                break;
            if(i % p[j]) {
                pk[t] = pk[p[j]];
            } else {
                pk[t] = pk[i] * p[j];
                break;
            }
        }
    }
}

int ans1[500005];
int ans2[500005];

void solve() {
    sieve();
    scanf("%d", &n);
    for(int i = 1, x; i <= n; ++i) {
        scanf("%d", &x);
        if(x == pk[x]) {
            ans1[i] = -1;
            ans2[i] = -1;
        } else {
            ans1[i] = pk[x];
            ans2[i] = x / pk[x];
        }
    }
    for(int i = 1; i <= n; ++i)
        printf("%d%c", ans1[i], " \n"[i == n]);
    for(int i = 1; i <= n; ++i)
        printf("%d%c", ans2[i], " \n"[i == n]);
    return;
}

This code spend 389ms to solve Problem D without any fast I/O.

To precompute some number's smallest prime factor, using The sieve of Euler, time complexity is O(A).

But it is not necessary to divided by smallest prime factor one by one, which using O(log(A)).

You can precompute number x has how many smallest prime factor at the same time.

It is not necessary to keep the amount of each type number unchanged, so just repalce all '2' to '1' is okay. Because it is a sudoku, each row, column and block has exactly one '1' and one '2'.

My solution to Problem D:

char s[15];
void TestCase() {
    for(int i = 1; i <= 9; ++i) {
        scanf("%s", s + 1);
        for(int j = 1; j <= 9; ++j) {
            if(s[j] == '2')
                s[j] = '1';
        }
        puts(s + 1);
    }
}

Just replace all '2' into '1'.

VERY OFFENSIVE

I think it is because that Problem A pretests are too weak. Many different main tests apend to system tests.

Keep coding, you will manage to get it after soon days.

Rating changes for the last round are temporarily rolled back. They will be returned soon.

I just found out that I also misread. Thank you.

I think it is similar to 1251E2 - Voting (Hard Version).

Link is here

Actually, the most similar thing between these two problems is "I can't achieve it during the round".

Change your each "else if" to "if", a point can fit 1 or 2 "if" branch.

You can hack yourself to append you stronger test case to the system test, a good chance to try it.

Greedyforce! Problem A,B,C and D are all greedy! Because I am a noble man, I don't like greed.

This is the reason why I failed in this round.

Your text to link here...

It means that there are some bugs hiding in your code. The bugs may be some easily mistakes such as OVERFLOW, FORGET TO CLEAR MEMORY. Your wrong code with these mistakes can pass pretest data, but have high probability FST. The hacker is helping you to improve your program.

This is the charm of Codeforces I think.

It is the first time I reach Purple, thanks to this interesting contest.

Thanks for your advice!

How to learn the culture of other countries?

Google (×) Codeforeces (√)

"Bonne chance et bonne note!"

It is correct?

dp[i][1]=dp[i-1][1]+cost(i,1); dp[i][2]=min(dp[i-1][1],dp[i-1][2])+cost(i,2); dp[i][3]=min(dp[i-1][1],dp[i-1][2],dp[i-1][3])+cost(i,3);

cost(i,j) means the cost if let the i-th problem be solved by the j-th programmer. Easily to know that cost(i,j)=1-(id[i]==j).

dp[i][1] from dp[i-1][1] means let [1,i] problems all be solved by programmer 1.

dp[i][2] from dp[i-1][1] means let [1,i-1] problems all be solved by programmer 1, but the i-th problem start to become be solved by programmer 2.

It means when you start to assign i-th problem to programmer 2, you cannot assign all j-th problem (j>i) to programmer 1.

You are also Chinese, so you can see this.

https://www.cnblogs.com/KisekiPurin2019/p/11854682.html

You can use dp to get the highest power of heroes which has at least i endurance.

        scanf("%d", &m);
        for(int i = 1, pi, si; i <= m; ++i) {
            scanf("%d%d", &pi, &si);
            p[si] = max(p[si], pi);
        }

        for(int i = n - 1; i >= 1; --i)
            p[i] = max(p[i], p[i + 1]);

p[i] is the highest power which can beat i monsters in just one day.

and then you can use greedy, each day try to move as more as possible.

        int i = 0, j = 0, rmq = -1, ans = 1;
        while(j < n) {
            ++j;
            rmq = max(rmq, a[j]);
            if(p[j - i] < rmq) {
                if(rmq > p[1]) {
                    ans = -1;
                    break;
                } else {
                    i = j - 1;
                    ++ans;
                    rmq = a[j];
                }
            }
        }

It means you have already beaten i-th monster, and you want to beat the j-th monster, today you move j-i blocks so the highest power is p[j-i], if p[j-1] < a[j], you need to wait until tomorrow and use your highest power hero p[1] to try to beat it.

dp[i][1] means the smallest cost which all [1,i] number return to its correct position and the i-th number(which is exactly i) belongs to the first Programmer.

dp[i][2] means ... belongs to the second Programmer. dp[i][3] means ... belongs to the third Programmer.

the ans is the smallest number among dp[n][1], dp[n][2] and dp[n][3].

if id[i]==1 and you want to let it still belong to the first Programmer, it cost none. Otherwise you will cost 1 unit.

int id[200005], dp[200005][4];

int main() {
    int A, B, C;
    scanf("%d%d%d", &A, &B, &C);
    for(int i = 1, ai; i <= A; ++i) {
        scanf("%d", &ai);
        id[ai] = 1;
    }
    for(int i = 1, bi; i <= B; ++i) {
        scanf("%d", &bi);
        id[bi] = 2;
    }
    for(int i = 1, ci; i <= C; ++i) {
        scanf("%d", &ci);
        id[ci] = 3;
    }

    int n = A + B + C;
    for(int i = 1; i <= n; ++i) {
        if(id[i] == 1) {
            dp[i][1] = dp[i - 1][1];
            dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]) + 1;
            dp[i][3] = min(dp[i - 1][1], min(dp[i - 1][2], dp[i - 1][3])) + 1;
        } else if(id[i] == 2) {
            dp[i][1] = dp[i - 1][1] + 1;
            dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]);
            dp[i][3] = min(dp[i - 1][1], min(dp[i - 1][2], dp[i - 1][3])) + 1;
        } else {
            dp[i][1] = dp[i - 1][1] + 1;
            dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]) + 1;
            dp[i][3] = min(dp[i - 1][1], min(dp[i - 1][2], dp[i - 1][3]));
        }
    }

    printf("%d\n", min(dp[n][1], min(dp[n][2], dp[n][3])));
    return 0;
}

Excuse me for interrupting you.

I think the Tutorial of Problem D may have something wrong.

The ok function has two return values.

if(need > v.size()) return false;

It is because var mid too small.

return sum <= s;

It is because var mid too large.

So how to keep monotonicity?

May someone help me? Thanks for your kindness.