Блог пользователя atcoder_official

Автор atcoder_official, история, 3 месяца назад, По-английски

We will hold JPRS Programming Contest 2026#2 (AtCoder Beginner Contest 470).

We are looking forward to your participation!

  • Проголосовать: нравится
  • -26
  • Проголосовать: не нравится

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I hope I can solve A to D.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I am from India, so I can participate in this contest, right?

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I hope I can solve D to F.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I hope that I can solve 5 problems, even 6! Of course, good luck to everyone!

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I am Chinese,I can fly!!!

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I hope I can solve A to D.Good luck to me,and good luck to everyone!

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

This is my first time to participate ABC contest,hopefully I can solve A to D,good luck to everyone!

I am Chinese,I can fly!!!

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I am Chinese,I can fly!!!

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I hope I can solve D ~ E

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I hope I can solve A to E.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I hope to do the E question.

(cross out)(I'm Chinese, I can fly.)

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I hope I can solve A to F.

And, I am Chinese, I can fly!!!

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I hope I can solve A to B.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

C is much harder than regular C (i skipped it and did D)

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

I think the difficulty of problem C is more than 600.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

After many days, I finally came back to play the game.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

rubbish task C, it should be task D. Downvote.

»
3 месяца назад, скрыть # |
← Rev. 2  
Проголосовать: нравится -18 Проголосовать: не нравится

why D is EZer than C???? and I am Chinese,I can fly!!!

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Why C is too hard

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Good problems, but I took too long to solve $$$C$$$ and $$$D$$$.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Are we sure C was actually a C problem??

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How is the answer for testcase 2 of $$$F$$$ = 18?

{1, 2, 3} and {4, 5, 6} are the components.

{1, 2, 3} = 3! / (1 * 1 * 1) = 6 permutations {4, 5, 6} = 3! / (1 * 1 * 1) = 6 permutations

6 * 6 = 36 is the answer?

»
3 месяца назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +10 Проголосовать: не нравится

C was so weird, it was a constraint analyzation problem, a pruned brute force works.

    cint(n, q);
    vi a(n);
    unordered_set<int> ind;
    int xr = 0;
    while (q--) {
      cint(type);
      if (type == 1) {
        cint(x);
        xr ^= a[x - 1];
        if (a[x - 1] == 0) {
          ind.insert(x - 1);
        }
        a[x - 1]++;
        xr ^= a[x - 1];

      } else {
        vector<int> ele;
        for (auto it : ind) {
          xr ^= a[it];
          if (a[it] == 1) {
            ele.push_back(it);
          }
          a[it]--;
          xr ^= a[it];
        }
        for (auto it : ele) {
          ind.erase(it);
        }
      }
      cout << xr << "\n";
    }
  }
  • »
    »
    3 месяца назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    People who doesn't even know what is a time complexity and who can calculate time complexity very well could solve it very easily. It's so funny that you need to be low skilled or high skilled to be able to solve this task, and if you wil be in the middle you will struggle a lot.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится -22 Проголосовать: не нравится

Rubbish C and hard E.Trash round.Downvote it please.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

C was OK I think. But G is too classical and E<F<G is unacceptable.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

I feel that question G is quite similar to this one.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

I dont know if this contest has tester or not, since its prepared by JPRS. But the problem position isnt sorted from easy to hard. Looking at the distribution of the solved number for each problems, its clear that D < C and F < E, not considering E < C because people can take too much time solving C and not looking at E for once.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

In fact, we might be overthinking C. If you know that things like 'std::set' or 'std::vector' can optimize away the empty values (**only storing the ones that exist**), then you can just directly simulate it according to its idea and it works. It looks terrifyingly like O(n^2), but in reality it's only O(q)

I deal with it at 1h 20min!!!

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

plz ban zyf2026,his code is actually from ai

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится +11 Проголосовать: не нравится

G is HDU4747.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Anyone explain problem C ...

  • »
    »
    3 месяца назад, скрыть # ^ |
    ← Rev. 3  
    Проголосовать: нравится +3 Проголосовать: не нравится

    if you maintain what positions have positive values and iterate over those positions when an operation of the second type happens, update XOR, and remove the values that become 0 from this list, for each iteration you do you cancel one operation of the first type, so basically operations of the first type will be applied O(q) times and will be cancelled O(q) times

    • »
      »
      »
      3 месяца назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      my code:

      int n, q;
      cin >> n >> q;
      vector<int> a(n);
      vector<int> changed;
      int XOR = 0;
      for (int i = 0; i < q; ++i) {
      	int type;
      	cin >> type;
      	if (type == 1) {
      		int j;
      		cin >> j;
      		--j;
      		XOR ^= a[j];
      		XOR ^= ++a[j];
      		if (a[j] == 1) {
      			changed.push_back(j);
      		}
      	}
      	else {
      		for (int j = (int)changed.size() - 1; j >= 0; --j) {
      			int idx = changed[j];
      			XOR ^= a[idx];
      			XOR ^= --a[idx];
      			if (a[idx] == 0) {
      				swap(changed[j], changed.back());
      				changed.pop_back();
      			}
      		}
      	}
      	cout << XOR << '\n';
      }
      
»
3 месяца назад, скрыть # |
 
Проголосовать: нравится -6 Проголосовать: не нравится

fuck the C problem

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Worst performance, i couldn't even solve C. :(

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится -16 Проголосовать: не нравится

ai can do this. The editor says that we can use set to protect the array of index which > 0. At the same time,we can protect the XOR sum.ai says that we can use 0/1 trie(the knowledge of e or upper one), or fenwick tree+protect the bits array(the knowledge of f or upper one).In a word,f**k the people who made this problem. I will share the 0/1 trie code which coded by deepseek.

Your code here...
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_BIT = 19; 
struct Trie {
    struct Node {
        int ch[2];
        int cnt;
        int xor_val;
        Node() : ch{0, 0}, cnt(0), xor_val(0) {}
    };
    vector<Node> nodes;
    int root;
    Trie() {
        nodes.reserve(12000000);
        nodes.emplace_back();
        nodes.emplace_back(); 
        root = 1;
    }
    void update(int u) {
        int l = nodes[u].ch[0], r = nodes[u].ch[1];
        nodes[u].cnt = (l ? nodes[l].cnt : 0) + (r ? nodes[r].cnt : 0);
        nodes[u].xor_val = 0;
        if (l) nodes[u].xor_val ^= (nodes[l].xor_val << 1);
        if (r) nodes[u].xor_val ^= ((nodes[r].xor_val << 1) | (nodes[r].cnt & 1));
    }
    void insert(int u, int bit, int val) {
        nodes[u].cnt++;
        if (bit == MAX_BIT) return;
        int b = (val >> bit) & 1;
        if (!nodes[u].ch[b]) {
            nodes.emplace_back();
            nodes[u].ch[b] = nodes.size() - 1;
        }
        insert(nodes[u].ch[b], bit + 1, val);
        update(u);
    }
    void erase(int u, int bit, int val) {
        nodes[u].cnt--;
        if (bit == MAX_BIT) return;
        int b = (val >> bit) & 1;
        erase(nodes[u].ch[b], bit + 1, val);
        update(u);
    }
    void sub_all(int u, int bit) {
        if (u == 0 || nodes[u].cnt == 0) return;
        if (bit == MAX_BIT) return;
        swap(nodes[u].ch[0], nodes[u].ch[1]);
        if (nodes[u].ch[1]) sub_all(nodes[u].ch[1], bit + 1);
        update(u);
    }
    void remove_all_zero(int u, int bit) {
        if (u == 0 || nodes[u].cnt == 0) return;
        if (bit == MAX_BIT) {
            nodes[u].cnt = 0;
            nodes[u].xor_val = 0;
            return;
        }
        remove_all_zero(nodes[u].ch[0], bit + 1);
        update(u);
    }
    int xor_sum() const {
        return nodes[root].xor_val;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, Q;
    cin >> N >> Q;
    vector<int> s(N + 1, -1);
    int offset = 0;
    Trie trie;
    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int x;
            cin >> x;
            int v = (s[x] == -1) ? 0 : max(0, s[x] - offset);
            if (v > 0) trie.erase(1, 0, v);
            int nv = v + 1;
            trie.insert(1, 0, nv);
            if (v == 0) s[x] = offset + 1;
            else s[x]++;
        } else {
            offset++;
            trie.sub_all(1, 0);          
            trie.remove_all_zero(1, 0);  
        }
        cout << trie.xor_sum() << '\n';
    }
    return 0;
}
»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I hava a better solution then official about Problem D: My solution link

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Every time there is a competition, I can see several users with black usernames on the first page of the leaderboard, and after a while, they disappear.

I hope that situations like the AI Beat Contest will not occur in the future. However, some people still try to use AI even though they know the chances of evading detection are slim.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I feel that C is harder than D , does anyone agree? :(

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

in my view, C is odd for its placement, E is verbose and hard to grasp, and G is simply too typical; the others are reasonably good though.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

such nice problems, especially C,D

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I think that C>>>>>>>>>>>>>>>>>>>>>>>>D

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

F > G > E hmmm....

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

I quickly completed problems A to D and started working on F, but I forgot to check the modulo answers, so I ultimately failed F

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

My first G, although it took me 97 minutes :)

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

C is quite hard to think, I thought like that,would store indices of >=1 , but did not implement it, because I thought that it would give tle , because iterate over each value of index

»
3 месяца назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

I believe I can solve A to E in future.And if I am lucky,I can get into my dream high school by competitions! And good luck to everyone who reads this comment! Also,I am a Chinese,I can fly!!!

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I C I F

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

No cheating but accounts were banned. :(

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

The C solution code of 0/1 trie coded by real human, me!

#include<bits/stdc++.h>
//#define int long long
#define rk(i,l,r) for(int i = l;i<=r;++i)
#define l(x) x<<1^inv(p)
#define r(x) (x<<1|1)^inv(p)
using namespace std;
const int N = 5e5+10,M=20;
signed n, q,op,x,dx,a[N];
struct trie{
	signed v=0,cnt=0;bool inv=0;
	#define v(x) tr[x].v
	#define cnt(x) tr[x].cnt
	#define inv(x) tr[x].inv 
}tr[N*M];
void update(int p)
{
	cnt(p)=cnt(l(p))+cnt(r(p));v(p)=0;
	if(cnt(l(p)))v(p)^=v(l(p))<<1;
	if(cnt(r(p)))v(p)^=(v(r(p))<<1)|cnt(r(p))&1;
}
void cg(int p, int u, int v, int step)
{
	cnt(p)+=v;
	if(step>=19)return;
	int b = (u>>step)&1;
	cg(p<<1|(b^inv(p)),u,v,step+1);
	update(p);
}
void sub1(int p, int step)
{
	if(step>=19)return;
	if(cnt(l(p)))sub1(l(p),step+1);
	inv(p)^=1;
	update(p);
}
void re0(int p, int step)
{
	if(step>=19){cnt(p)=v(p)=0;return;}
	if(cnt(p))re0(l(p),step+1);
	if(cnt(p))update(p);
}
signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	while(q--)
	{
		cin>>op;op--;
		if(op)sub1(1,0),re0(1,0),dx++;
		else
		{
			cin>>x;
			int k= max(0,a[x]-dx);
			if(k)cg(1,k,-1,0);
			cg(1,k+1,1,0);
			if(!k)a[x]=dx+1;
			else a[x]++;
		}cout<<v(1)<<'\n';
	}
	return 0;
 } 
»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

i think this C is hard i used 1 min to solve A,3 mins to solve B,but used 40 mins to solve C MIND YOU,I'm Chinese i can fly