제출 #1228419

#제출 시각아이디문제언어결과실행 시간메모리
1228419amine_arouaHieroglyphs (IOI24_hieroglyphs)C++20
0 / 100
31 ms7444 KiB
#include "hieroglyphs.h" #include <bits/stdc++.h> using namespace std; int len = 0; int N = 0 , M = 0 , oneA , oneB , zerA , zerB; vector<vector<int>> posA , posB; vector<int> find_ucs(int x , vector<int> A , vector<int> B) { vector<int> cur; int mn = min((int)posA[x].size() , (int)posB[x].size()); if(mn == 0) { int nb = min((int)posA[x^1].size() , (int)posB[x^1].size()); while(nb--) cur.push_back(x^1); return cur; } int prv = min(posA[x][0] , posB[x][0]); while(prv--) cur.push_back(x^1); cur.push_back(x); int i = 0; int a = posA[x][i] , b = posB[x][i]; int cntA = posA[x^1].end() - upper_bound(posA[x^1].begin() , posA[x^1].end() , a); int cntB = posB[x^1].end() - upper_bound(posB[x^1].begin() , posB[x^1].end() , b); prv = min(cntA , cntB); for( ; i < mn ; i++) { a = posA[x][i] , b = posB[x][i]; cntA = posA[x^1].end() - upper_bound(posA[x^1].begin() , posA[x^1].end() , a); cntB = posB[x^1].end() - upper_bound(posB[x^1].begin() , posB[x^1].end() , b); int now = min(cntA , cntB); while(now != prv) { cur.push_back(x^1); prv--; } cur.push_back(x); } return cur; } std::vector<int> ucs(std::vector<int> A, std::vector<int> B) { N = (int)A.size(); M = (int)B.size(); posA.assign(2 ,vector<int>(N)); posB.assign(2 ,vector<int>(M)); zerA = 0 ,zerB = 0; for(int i = 0 ; i < N ; i++) { posA[A[i]].push_back(i); if(A[i] == 0) zerA++; } for(int i = 0 ; i < M ; i++) { posB[B[i]].push_back(i); if(B[i] == 0) zerB++; } oneA = N - zerA; oneB = M - zerB; len = min(zerA , zerB) + min(oneA , oneB); vector<int> a = find_ucs(0 , A , B); vector<int> b = find_ucs(1 , A , B); if(a != b || (int)a.size() != len) { return {-1}; } return a; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...