Skip to content

Commit cb140d9

Browse files
OneCodeMonkeyOneCodeMonkey
committed
update
1 parent cc7111e commit cb140d9

7 files changed

+215
-0
lines changed

‎codeForces/Codeforces_1621A_Stable_Arrangement_of_Rooks.java‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
// AC: 249 ms
2+
// Memory: 800 KB
3+
// Constructive.
4+
// T:O(sum(ni^2)), S:O(max(ni))
5+
//
6+
import java.util.Scanner;
7+
8+
public class Codeforces_1621A_Stable_Arrangement_of_Rooks {
9+
public static void main(String[] args) {
10+
Scanner sc = new Scanner(System.in);
11+
int t = sc.nextInt();
12+
for (int i = 0; i < t; i++) {
13+
int n = sc.nextInt(), k = sc.nextInt(), index = 0;
14+
if (k > (n + 1) / 2) {
15+
System.out.println(-1);
16+
} else {
17+
for (int j = 0; j < n; j++) {
18+
String row = ".".repeat(n);
19+
if (j % 2 == 1) {
20+
System.out.println(row);
21+
continue;
22+
}
23+
if (k > 0) {
24+
if (index == 0) {
25+
row = "R" + ".".repeat(n - 1);
26+
} else {
27+
row = ".".repeat(index) + "R" + ".".repeat(n - 1 - index);
28+
}
29+
index += 2;
30+
k--;
31+
}
32+
System.out.println(row);
33+
}
34+
}
35+
}
36+
}
37+
}

‎codeForces/Codeforces_1742E_Scuza.java‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
// AC: 1390 ms
2+
// Memory: 31200 KB
3+
// Binary Search, Or using TreeMap.
4+
// T:O(sum(ni)), S:O(max(ni))
5+
//
6+
import java.util.Scanner;
7+
import java.util.TreeMap;
8+
9+
public class Codeforces_1742E_Scuza {
10+
public static void main(String[] args) {
11+
Scanner sc = new Scanner(System.in);
12+
int t = sc.nextInt();
13+
for (int i = 0; i < t; i++) {
14+
int n = sc.nextInt(), q = sc.nextInt(), maxVal = -1;
15+
long[] prefixSum = new long[n + 1];
16+
TreeMap<Integer, Integer> valToIndex = new TreeMap<>();
17+
for (int j = 0; j < n; j++) {
18+
int a = sc.nextInt();
19+
maxVal = Math.max(maxVal, a);
20+
valToIndex.putIfAbsent(maxVal, j);
21+
prefixSum[j + 1] = prefixSum[j] + a;
22+
}
23+
StringBuilder ret = new StringBuilder();
24+
for (int j = 0; j < q; j++) {
25+
int k = sc.nextInt();
26+
Integer index = valToIndex.ceilingKey(k + 1);
27+
if (index == null) {
28+
ret.append(prefixSum[n]);
29+
} else {
30+
ret.append(prefixSum[valToIndex.get(index)]);
31+
}
32+
if (j != q - 1) {
33+
ret.append(" ");
34+
}
35+
}
36+
37+
System.out.println(ret);
38+
}
39+
}
40+
}

‎codeForces/Codeforces_2008B_Square_or_Not.java‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
// AC: 296 ms
2+
// Memory: 900 KB
3+
// String.
4+
// T:O(sum(ni)), S:O(max(ni))
5+
//
6+
import java.util.Scanner;
7+
8+
public class Codeforces_2008B_Square_or_Not {
9+
public static void main(String[] args) {
10+
Scanner sc = new Scanner(System.in);
11+
int t = sc.nextInt();
12+
for (int i = 0; i < t; i++) {
13+
int n = sc.nextInt(), sqrtN = (int) Math.sqrt(n);
14+
String s = sc.next();
15+
boolean ret = false;
16+
if (sqrtN * sqrtN == n) {
17+
boolean flag = true;
18+
for (int j = 0; j < sqrtN; j++) {
19+
if (!flag) {
20+
break;
21+
}
22+
if (j == 0 || j == sqrtN - 1) {
23+
for (int k = 0; k < sqrtN; k++) {
24+
if (s.charAt(j * sqrtN + k) == '0') {
25+
flag = false;
26+
break;
27+
}
28+
}
29+
} else {
30+
if (s.charAt(j * sqrtN + 0) == '0' || s.charAt(j * sqrtN + sqrtN - 1) == '0') {
31+
flag = false;
32+
break;
33+
}
34+
for (int k = 1; k < sqrtN - 1; k++) {
35+
if (s.charAt(j * sqrtN + k) == '1') {
36+
flag = false;
37+
break;
38+
}
39+
}
40+
}
41+
}
42+
ret = flag;
43+
}
44+
45+
System.out.println(ret ? "Yes" : "No");
46+
}
47+
}
48+
}

‎codeForces/Codeforces_2008C_Longest_Good_Array.java‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
// AC: 374 ms
2+
// Memory: 900 KB
3+
// Math.
4+
// T:O(n), S:O(1)
5+
//
6+
import java.util.Scanner;
7+
8+
public class Codeforces_2008C_Longest_Good_Array {
9+
public static void main(String[] args) {
10+
Scanner sc = new Scanner(System.in);
11+
int t = sc.nextInt();
12+
for (int i = 0; i < t; i++) {
13+
int l = sc.nextInt(), r = sc.nextInt(), range = r - l, ret = 1;
14+
if (range > 0) {
15+
int sqrtN = (int) Math.sqrt(2 * range);
16+
if (sqrtN * (sqrtN + 1) / 2 <= range) {
17+
ret = sqrtN + 1;
18+
} else {
19+
ret = sqrtN;
20+
}
21+
}
22+
23+
System.out.println(ret);
24+
}
25+
}
26+
}

‎codeForces/Codeforces_2009A_Minimize.java‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
// AC: 280 ms
2+
// Memory: 400 KB
3+
// .
4+
// T:O(t), S:O(1)
5+
//
6+
import java.util.Scanner;
7+
8+
public class Codeforces_2009A_Minimize {
9+
public static void main(String[] args) {
10+
Scanner sc = new Scanner(System.in);
11+
int t = sc.nextInt();
12+
for (int i = 0; i < t; i++) {
13+
int a = sc.nextInt(), b = sc.nextInt();
14+
System.out.println(b - a);
15+
}
16+
}
17+
}

‎leetcode_solved/leetcode_3375_Minimum_Operations_to_Make_Array_Values_Equal_to_K.java‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
// Runtime 5 ms Beats 100.00%
2+
// Memory 44.92 MB Beats 100.00%
3+
// To make all equal, the final result must be <= smallest one.
4+
// T:O(n + klogk), S:O(k), k = unique numbers.
5+
//
6+
class Solution {
7+
public int minOperations(int[] nums, int k) {
8+
HashSet<Integer> record = new HashSet<>();
9+
for (int num : nums) {
10+
record.add(num);
11+
}
12+
List<Integer> unique = new ArrayList<>(record);
13+
Collections.sort(unique);
14+
15+
if (k > unique.get(0)) {
16+
return -1;
17+
} else if (k == unique.get(0)) {
18+
return unique.size() - 1;
19+
} else {
20+
return unique.size();
21+
}
22+
}
23+
}

‎leetcode_solved/leetcode_3379_Transformed_Array.java‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
// Runtime 1 ms Beats 100.00% Analyze Complexity
2+
// Memory 44.76 MB Beats 100.00%
3+
// Array.
4+
// T:O(n), S:O(1)
5+
//
6+
class Solution {
7+
public int[] constructTransformedArray(int[] nums) {
8+
int len = nums.length;
9+
int[] ret = new int[len];
10+
for (int i = 0; i < len; i++) {
11+
if (nums[i] == 0) {
12+
ret[i] = nums[i];
13+
} else if (nums[i] > 0) {
14+
int index = (i + nums[i]) % len;
15+
ret[i] = nums[index];
16+
} else if (nums[i] < 0) {
17+
int index = (i + nums[i]) < 0 ? (len + (i + nums[i]) % len) : (i + nums[i]);
18+
ret[i] = nums[index];
19+
}
20+
}
21+
22+
return ret;
23+
}
24+
}

0 commit comments

Comments
 (0)