main.cpp (2765B)
1 #include <iostream> 2 #include <vector> 3 #include <unordered_set> 4 #include <unordered_map> 5 #include <algorithm> 6 #include <queue> 7 8 #define ll long long 9 10 // spam emote triangle of size k 11 // it's 2k-1 messages 12 13 // k = 3 is: 14 15 // e 16 // e e 17 // e e e 18 // e e 19 // e 20 21 // k = 4 is: 22 23 // e 24 // e e 25 // e e e 26 // e e e e 27 // e e e 28 // e e 29 // e 30 31 // k = 5 is: 32 33 // e 34 // e e 35 // e e e 36 // e e e e 37 // e e e e e 38 // e e e e 39 // e e e 40 // e e 41 // e 42 43 // Auto moderator of the current chat will ban you right after you spam at least x emotes in succession 44 // e is an emote above 45 // assume only user in chat is us 46 // how many messages will we write before being banned 47 // message is a full line 48 // banned message is also included in sum of messages sent 49 50 51 // k = 3 52 // this has 5*1 + 3*1 + 1*1 = 9 emotes 53 54 // k = 5 55 // this has 7*1 + 5*1 + 3*1 + 1*1 = 16 emotes 56 57 // NOTE: This includes the midpoint line 58 // top half sum == 59 // lineNumber = min(lineNum, k) 60 // (lineNumber + 1) * (lineNumber / 2) 61 // NOTE: lineNumber / 2 is floating point 62 63 // IFF lineNumber > k 64 // bottom half sum = 65 // (deltaToEnd + 1) * (deltaToEnd / 2) 66 67 68 // Then, we do a binary search to find the first value > target 69 70 using namespace std; 71 72 73 ll computeAbove(ll lineNum, ll k) { 74 ll lineNumber = min(lineNum,k); 75 ll delta = 0; 76 77 // this is always correct because the +1 will make line number evenly div by 2. 78 if(lineNumber%2 == 1) { 79 delta = (lineNumber+1) / 2; 80 } 81 82 ll topHalf = ((lineNumber+1) * (lineNumber/2)) + delta; 83 84 ll bottomHalfMissing = -1; 85 86 if(lineNum > k) { 87 ll delta = ((k*2)-1) - (lineNum); 88 ll dt = 0; 89 90 if(delta%2 == 1) { 91 dt = (delta+1) / 2; 92 } 93 94 bottomHalfMissing = (delta + 1) * (delta / 2) + dt; 95 } 96 if(bottomHalfMissing == -1) { 97 return topHalf; 98 } else { 99 return topHalf + ((topHalf-k) - bottomHalfMissing); 100 } 101 } 102 103 void binarySearchFor(ll k, ll target, ll left, ll right) { 104 105 ll midPoint = left + ((right - left)/2); 106 107 if(midPoint == left) { 108 ll score = computeAbove(midPoint, k); 109 if(score >= target) { 110 cout << midPoint << endl; 111 } else { 112 cout << right << endl; 113 } 114 return; 115 } 116 117 ll score = computeAbove(midPoint, k); 118 119 if(score < target) { 120 binarySearchFor(k,target,midPoint,right); 121 return; 122 } 123 124 if(score == target) { 125 cout << midPoint << endl; 126 return; 127 } 128 129 if(score > target) { 130 binarySearchFor(k,target,left,midPoint); 131 return; 132 } 133 134 135 } 136 137 138 int main() { 139 140 ll testCases, k,m; 141 cin >> testCases; 142 143 for(ll z = 0; z < testCases; ++z) { 144 cin >> k; 145 cin >> m; 146 binarySearchFor(k,m,1, (2*k) - 1); 147 } 148 149 }