Page 6 I created every stack using pointers, but nodes in this stack saved data of ten last pushed elements, not of one last. So this is a stack of arrays and not the stack of single elements. Also I had an additional array of int[1000], that showed how many positions in last node of each stack is already used. Conclusion: you need to do such a struct of that has an array of ten elements and a pointer to previous node. On every push-call you should create another node(if previous is full) and add an element on the first open space of node, then increase the number of used positions. On every pop-call you should go to previous node and delete current node(if current node is empty) and print the last element of node, then decrease the number of used positions. Hope it'll help you. And I apologize for my poor english) Thank you!, now I got AC. =) I spent 3 hours on it.But I find it is expected to use "short" at last!!! How to solve this problem using c++ ? My pick is #MLE 14. I use (10^5 + 1000)*4 + 10^5 * 2 = 589,84375 kilobytes of memory. I have no idea how to optimize it even more( Edited by author 20.08.2020 02:34 Edited by author 20.08.2020 02:34 I solved this problem. I can only suggest you to think about headers.In this problem this cost a lot. To save memory,you must count total amount of bits that you need and use nearly that amount of space. Use bitwise operators to write and read numbers. Edited by author 21.08.2020 01:15 Earlier this problem has got a strict result about a lot of realizations - about two years ago I have a submit which got a MLE 10 (7603331), but now this code on same compiler (VS C++ 2017) have only 252 KB! But on G++ - MLE 1. Similarly - my older AC code now have less memory. How it works? Why it has got such difference in memory after two years and between compilers? Changing virtual machine get this strange result? I think there is a bug with measuring memory used just a joke Edited by author 18.09.2019 20:08 I tried so many time until I change `#include<bits/stdc++.h>` to `#include<stdio.h>`. And then I did a small experience: for the same code, Visual C++ 2017 -- 612 KB Visual C 2017 -- 620 KB GCC 7.1 / Clang++ 4.0.1 -- 652 KB G++ 7.1 -- 700 KB Hope it helps~ C++ costs 200 kb (Visual C++ and 400 kb other compilers). #include<bits/stdc++.h> using namespace std; int main(){ long N,i,stack_id,num; string code; const string push="PUSH"; vector< stack<int> > stacks; cin>>N; for(i=0;i<N;i++){ cin>>code; if(code==push){ cin>>stack_id>>num;
if(stack_id>stacks.size()){ stacks.push_back( stack<int>() ); } stacks[stack_id-1].push(num);
} else{ cin>>stack_id; cout<<stacks[stack_id-1].top()<<"\n"; stacks[stack_id-1].pop(); } }
return 0; } I get correct output on the sample code though. Try test: 1 push 900 1 Btw, have you seen memory limit for this task? You need to be able to execute 100,000 pushes of 4-bytes integers (in one stack and in random stacks) - 400 Kb of data + empty program requires ~200K. Your implementation should fail (memory limit) during vector resize. #include <iostream> using namespace std; struct duy{ long long x; int y; }; int n,x,last[1001]; long long y; duy m[100001]; char s[5]; int main() { cin.tie(NULL); cout.tie(NULL); cin>>n; for(int i=1; i<=n; i++){ cin>>s>>x; if(s[1]=='U'){ cin>>y; m[i].x=y; m[i].y=last[x]; last[x]=i; } else{ cout<<m[last[x]].x; last[x]=m[last[x]].y; } } } By task description, B is an integer (0 ≤ B ≤ 10^9). So "int x", not "long long x". But it shouldn't be enough. Please estimate (or just type from local run) sizeof(duy) and sizeof(m). Then read task memory restriction. Assume that even "empty main()" program spends about 100 Kb (see successful runs of "1000 A+B" problem for your compiler). In this case duy can hold not only one x, but bucket - ~30 values for example. More, 30 bits are required to save B. So it's possible to save 32 values into "int x[30]" array. Edited by author 10.03.2017 15:50 Didn't notice that problem is not for Java, so I solved it. Maybe someone will need the solution. Solution without checking of stacks for emptiness. import java.util.ArrayList; import java.util.HashMap; import java.util.Scanner; import java.util.StringTokenizer; public class HelloWorld { public static void main (String[] args) { HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>(); Scanner reader = new Scanner(System.in); int n = reader.nextInt(); reader.nextLine(); for (int i = 0; i < n; i++) { String command = reader.nextLine(); StringTokenizer tokenizer = new StringTokenizer(command); command = tokenizer.nextToken(); if ("PUSH".equals(command)) { int key = Integer.parseInt(tokenizer.nextToken()); int value = Integer.parseInt(tokenizer.nextToken()); if (map.containsKey(key)) { map.get(key).add(0, value); } else { map.put(key, new ArrayList<Integer>()); map.get(key).add(0, value); } } else if ("POP".equals(command)) { int key = Integer.parseInt(tokenizer.nextToken()); if (map.containsKey(key)) { System.out.println(map.get(key).get(0)); map.get(key).remove(0); } } } } } Edited by author 31.10.2016 23:24 Edited by author 31.10.2016 23:26 Look at this, and remember magic number. #include<stdio.h> using namespace std; const int max_stacks = 1000; const int max_blocks = 6000; // magic number const int block_size = 25; int block[max_blocks][block_size]; int current_top[max_blocks]; int next_block[max_blocks]; int prev_block[max_blocks]; int free_blocks[max_blocks]; int fb_top=-1; int head[max_stacks]; int tail[max_stacks]; int full_size[max_stacks]; int mem_sz = max_stacks*3 + max_blocks*4 + max_blocks*block_size; int stn; int i; int n; int value; void init() { for (i=0;i<max_stacks;i++) { head[i] = -1; tail[i] = -1; full_size[i] = 0; } for (i=0;i<max_blocks;i++) { current_top[i] = -1; next_block[i] = -1; prev_block[i] = -1; } for (i=0;i<max_blocks;i++) { free_blocks[i] = i; } fb_top = max_blocks-1; } void raise() { int x = 42; int y = (x-x)/(x-x); int z = x/y; fb_top = z; } int get_free_block() { if (fb_top==-1) raise(); return free_blocks[fb_top--]; } void clear_tail () { if (tail[stn]==-1) raise(); int b = tail[stn]; tail[stn] = next_block[b]; prev_block[tail[stn]] = -1; full_size[stn]-=block_size; if (full_size<0) raise(); free_blocks[++fb_top] = b; current_top[b] = -1;
next_block[b] = -1; prev_block[b] = -1; } void push() { if (head[stn]==-1) { int free = get_free_block(); head[stn] = free; tail[stn] = free;
current_top[free] = 0; block[free][0] = value; next_block[free] = -1; prev_block[free] = -1; } else if (current_top[head[stn]]==block_size-1) { if (full_size[stn]>n-i+2*block_size) { clear_tail(); } int free = get_free_block(); current_top[free] = 0; block[free][0] = value; next_block[head[stn]] = free; prev_block[free] = head[stn]; head[stn] = free; } else { block[head[stn]][++current_top[head[stn]]] = value; } full_size[stn]++; } int pop() { if (current_top[head[stn]]==-1) raise; int ans = block[head[stn]][current_top[head[stn]]--]; if (current_top[head[stn]]==-1) { int cur = head[stn]; head[stn] = prev_block[head[stn]]; next_block[head[stn]]=-1; next_block[cur] = -1; prev_block[cur] = -1; free_blocks[++fb_top] = cur; } full_size[stn]--; return ans; } ok, if magic number == 6000, it got WA 15 magic number == 6004, WA 15 magic number == 6005, AC magic number == 6006, AC magic number == 6500, WA 15 How it can be? I hope somebody will explain me what's wrong with my program, cause I really dont understand why i get out of memory (900KB) when my program should use only about 700KB (no more than 750KB definetly!). So pls help me smb. Now i try to explain my problem. The only memory i use, i define out of main scope and i dont use any dynamic allocations. So, the definition looks like: unsigned int length[MAXIMUMSTACKS]; unsigned int maxlength[MAXIMUMSTACKS]; unsigned int base[MAXIMUMSTACKS]; unsigned int stackPtr[MAXIMUMSTACKS]; unsigned char opbuf[OPSIZE * MAXOP]; unsigned int stack[MAXOP / 2]; where MAXIMUMSTACKS = 1000, OPSIZE = 5, MAXOP = 100000. So, let's count all memory we may use: 4*1000 + 4*1000 + 4*1000 + 4*1000 + 500000 + 4*50000 = 16*1000 + 500000 + 200000 = 716000 bytes! I is about 700KB to be honest. So, i dont inderstand, why my program get Memory Limit Error and use (as Timus says) 900KB(!). Pls, help me to fix it. Tell me what i dont understand. I give you the code of programm below. #include <stdio.h> #include <stdlib.h> #include <string.h> #define MASK(k) ((1 << k) - 1) #define OPSIZE 5 #define POPCODE 1000000001 #define MAXIMUMSTACKS 1000 #define MAXOP 100000 unsigned int N; unsigned int length[MAXIMUMSTACKS]; unsigned int maxlength[MAXIMUMSTACKS]; unsigned int base[MAXIMUMSTACKS]; unsigned int stackPtr[MAXIMUMSTACKS]; unsigned char opbuf[OPSIZE * MAXOP]; unsigned int stack[MAXOP / 2]; char op[5]; unsigned short stnum; unsigned int value; unsigned int indx; int main(int argc, char *argv[]) { // freopen("input.txt", "r", stdin); // init scanf("%u", &N); memset(opbuf, 0, N * OPSIZE); memset(length, 0, MAXIMUMSTACKS * sizeof(unsigned short)); memset(maxlength, 0, MAXIMUMSTACKS * sizeof(unsigned short)); // fill opbuf for (unsigned int i = 0; i < N; ++i) { scanf("%s%hu", op, &stnum); --stnum; indx = OPSIZE * i; opbuf[indx] = *((unsigned char*)&stnum); opbuf[indx + 1] = *((unsigned char*)&stnum + 1) & MASK(2); if (op[1] == 'U') { scanf("%u", &value); value = (value << 2); for (unsigned int j = 0; j < 4; ++j) opbuf[indx + 1 + j] += *((unsigned char*)&value + j); ++length[stnum]; if (length[stnum] > maxlength[stnum]) { maxlength[stnum] = length[stnum]; if (maxlength[stnum] > MAXOP / 2) maxlength[stnum] = MAXOP / 2; } } else { value = (POPCODE << 2); for (unsigned int j = 0; j < 4; ++j) opbuf[indx + 1 + j] += *((unsigned char*)&value + j); --length[stnum]; } } // create big memory block for stacks unsigned int prevLength = 0; unsigned int prevBase = 0; for (unsigned int i = 0; i < MAXIMUMSTACKS; ++i) { if (maxlength[i] == 0) continue; base[i] = prevBase + prevLength; stackPtr[i] = base[i]; prevBase = base[i]; prevLength = maxlength[i]; } // process through opbuf for (unsigned int i = 0; i < N; ++i) { stnum = 0; value = 0; indx = OPSIZE * i; stnum += opbuf[indx]; stnum += ((opbuf[indx + 1] & MASK(2)) << 8); for (unsigned int j = 0; j < 4; ++j) *((unsigned char*)&value + j) = opbuf[indx + 1 + j]; value = ((value >> 2) & 0x3fffffff); if (value == POPCODE) { if (stackPtr[stnum] == base[stnum]) { stackPtr[stnum] = base[stnum] + maxlength[stnum] - 1; } else { stackPtr[stnum]--; } printf("%u\n", stack[stackPtr[stnum]]); } else { stack[stackPtr[stnum]] = value; if (stackPtr[stnum] == base[stnum] + maxlength[stnum] - 1) stackPtr[stnum] = base[stnum]; else stackPtr[stnum]++; } } return 0; } Edited by author 20.08.2015 16:44 source program only uses about 300KB + 700 = MLE. So you should use about 520000 Byte = 500 KB .My advice is to use a chunk of memory that we split into pieces (for example size 8) in the first part where you keep information about previous segment of the current stack and keep the information in the stack remaining 7.Be excused my english, if you do not clear reply and will present in more detail. Allocated big buffers: commands - 5*MAXOP = 500K stack - 4*MAXOP/2 = 250K Total - 750K buffers only As empty C++ program takes about 100K you have MLE If you wont analyze save commands stack - 4*MAXOP = 500K (all pushes) + some chunks info How your program will work if input sequence is something like 33K * "PUSH 1 100" // less then MAX_OP/2 33K * "PUSH 2 100" // less then MAX_OP/2 33K * "PUSH 3 100" // less then MAX_OP/2 POP 1 POP 2 POP 3 Your program should allocate 3 stacks with total 99K size in the 50K array. Если вы поменяли компиляторы, то нужно сделать реджардж по задаче т.к. мои старые решения уже не проходят (да и вообще, если пересдавать старые АС, то память в них увеличилась, а вот время как-то непонятно ведет, где-то упало до 0.001, а там где было 0.5 сейчас стало 1.5) Remember to remove any possible padding of the struct: for example, in MSVC do #pragma pack(push, 1) before the struct definition. You can post blogs to codeforces or topcoder or etc. #include<vector> #include<stack> #include<iostream> int main() { int noOfInstructions = 0; std::cin>> noOfInstructions; std::vector< std::stack< int > > myVectorOfStacks; myVectorOfStacks.reserve( 1001 ); for( int inx = 0; inx < 1001; ++inx ) { myVectorOfStacks.push_back( std::stack<int>() ); } char instruction[3]; int stackNumber = 0; int stackValue = 0;
for( int inx = 0; inx < noOfInstructions; ++inx ) { std::cin>> instruction; std::cin>> stackNumber; std::stack< int > & tempStack = myVectorOfStacks.at( stackNumber );
if( instruction[1] == 'U' ) { std::cin>> stackValue; tempStack.push( stackValue ); } else { std::cout<< tempStack.top()<< "\n"; tempStack.pop(); } } return 0; } #include<vector> #include<stack> #include<iostream> int main() { int noOfInstructions = 0; std::cin>> noOfInstructions; std::vector< std::stack< int > > myVectorOfStacks; myVectorOfStacks.reserve( 1001 ); for( int inx = 0; inx < 1001; ++inx ) { myVectorOfStacks.push_back( std::stack<int>() ); } char instruction[3]; int stackNumber = 0; int stackValue = 0;
for( int inx = 0; inx < noOfInstructions; ++inx ) { std::cin>> instruction; std::cin>> stackNumber; std::stack< int > & tempStack = myVectorOfStacks.at( stackNumber );
if( instruction[1] == 'U' ) { std::cin>> stackValue; tempStack.push( stackValue ); } else { std::cout<< tempStack.top()<< "\n"; tempStack.pop(); } } return 0; } i got 0.531 sec for this code #include <stdio.h> #include <stdlib.h> typedef unsigned int type; struct stack{ type* value; int cnt; int size; }; #define delta 4 #define getnum(num) do {\ (num) = 0; \ char c; \ while(1) { \ c = fgetc(stdin); \ if((c<'0')||(c>'9')) break; \ (num)*=10; \ (num)+=c-'0'; \ }\ }while(0) #define putnum(num) do { \ char str[16]; \ char *it = &str[15];*it = 0; \ if((num)==0) { fputc('0', stdout); } \ else { \ while(num) { \ --it; \ *it = (char)((num)%10)+'0'; \ (num)/=10; \ } \ while(*it) { \ fputc(*it, stdout); \ ++it; \ } \ }\ fputc('\n', stdout); \ } while(0); struct stack st[1000] = {0}; int main() { int cnt; getnum(cnt); while(cnt--){ int id; char c,i; i=0; while((c = getchar())!=' ') ++i; getnum(id); --id; if(i>3) { st[id].cnt++; if(st[id].cnt > st[id].size) { st[id].size+=delta; st[id].value = (type*)realloc(st[id].value, st[id].size*sizeof(type)); } getnum(st[id].value[st[id].cnt-1]); } else { st[id].cnt--; putnum(st[id].value[st[id].cnt]); if(st[id].cnt+delta<st[id].size) { st[id].size-=delta; st[id].value = (type*)realloc(st[id].value, st[id].size*sizeof(type)); } } } return 0; } if set delta to 6, then i got MLE on test #12 =/ i broke my brain. Sorry for my English у меня точно такой же алгоритм :) и точно такая же проблема :) Page 5 Better correct the memory usage by Java programs. You can simply decrease memory by 200 KB or just increase memory limits for some problems that can't be solved on Java or C#. Язык запрещен для данной задачи Language is not allowed for this problem Edited by author 26.04.2013 17:32 I also can't understood why Java is disallowed now. Even if java solution is not so fast as C/C++/Pascal, it's iteresting to make some optimisations to java solution, to get accepted. Please, accept Java for this problem. Now empty Java 1.7 program takes only 116Kb, so 750kb would be enought to make a solution. Edited by author 05.07.2013 13:04 Pages: 6 5 4 3 2 1 Previous |
|